UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3556. [Ctsc2014] 插线板

Statistics 下载数据

Description

 Allison有非常多的电子设备,比如iMac,iPod,iPhone和iPad。所以她准备购买插线板来给电子设备充电。在做了大量的网络调研后,

Allison拔线了一款美丽精巧的天翼牌排插(如左下图所示)。在见到这个插线板的第一眼,Allison就被它的境美造型所吸引,
于是她一次性购买了n个这种型号的插线板。 
 可是问题也随之而来,Allison的家中只有一个插座,她需要通过插线板的连接将电一层一层地导出(如右上图所示)。 
插线板的连接方式是树形结构的:每个插线板的插头插在另一个插线板的插空中(除了根节点),插线板的连接不允许构成环。 
每个插线板有火线,零线,地线三根导线,随着插线板数量的增加、倒显得磨损,电路中导线与导线之间接触产生的电阻已经到了
不能被忽视的地步。 
如何来描述插线板的树形结构以及导线之间的电阻关系呢?Allison思考出来一个数学模型:用ai代表第i个插线板的编号,fi代表
第i个插线板的插头所差的插线板(即ai在树中的父亲),1代表火线,2代表零线,3代表地线,则整个网络的电阻可以用
R(ai,fi,x,y)(x,y∈{1,2,3})来描述,它代表ai的x线与fi的y线之间的电阻值(在这个数学模型中,Allison认为火线和领先也是
可能连接并且产生电阻的)下面是一个例子: 
 
由于时间的推移,导线与导线之间的电阻还可能发生变化。现在,Allison想知道在插线板树形电路中,当前时刻ai插线板的x线和
aj插线板的y线之间的电阻式多少。规定插线板的树根节点不再插向其他插线板,且编号为1。 

Input

 第一行包含一个正整数n,表示插线板的个数。 

接下来4(n-1)行,每4行为一个块。 
第i块的第一行为一个整数fi【注:原题如此。实际应该是fi+1,下同】,表示编号为i+1的插线板的父亲为fi【注:同上】插线板。 
接下来一个3*3的矩阵gxy,第x行第y个数表示编号为i+1的插线板的x线和fi【注:同上】的y线之间的电阻的倒数。 
接下来一个整数q,表示q个操作数。 
第一个整数位k,若k=1则接下来包含四个整数ai,xi,xj,g,表示将ai插线板的xi线与ai插线板的父亲fi
【注:原题如此。实际应该是fai】的xj线之间的电阻值改为g的倒数。保证2<=ai<=n。 
若k=2,则接下来包含四个整数ai,xi,aj,xj,表示询问ai插线板的xi线与aj插线板的xj线之间的电阻大小。保证ai≠aj。 

Output

对每个询问,输出一行实数,表示两条线之间的电阻。 

若|(选手输出-标准输出)/标准输出|<=10^-3,则被认为该电阻值正确,若所有电阻值皆正确,则可获得该测试点的得分。 

Sample Input

3
1
6 7 1
4 1 8
8 3 3
2
7 5 8
10 5 7
10 5 5
10
1 3 1 2 2
1 2 2 3 5
2 3 2 2 2
1 2 3 2 5
1 3 1 2 3
2 1 2 2 3
1 3 2 1 2
2 2 1 1 1
1 2 1 2 5
2 3 1 1 2

Sample Output

0.083836
0.095256
0.078828
0.146900

Hint

 对于所有测试数据,输入保证是一棵树。0<输入中电阻的倒数<=10。 


测试点编号            特点

   1-6          n<=100,q<=1000,保证输入中只有查询没有修改

   7-10         n<=1000,q<=1000,保证数据是一条链

   11-16        n<=10000,q<=10000,保证数的高度不超过30

   17-20        n<=10000,q<=10000

Source

鸣谢Vfleaking提供Spj