3556 - [Ctsc2014] 插线板
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，则被认为该电阻值正确，若所有电阻值皆正确，则可获得该测试点的得分。
Examples
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
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