#P3556. [Ctsc2014] 插线板
[Ctsc2014] 插线板
[CTSC2014] 插线板
题目描述
Allison 有许多要充电的电子设备,她为此购买了 个插线板。她家里只有一个插座。除了接到这个插座的根插线板,其余每个插线板都接到另一个插线板上,构成一棵树。根插线板的编号为 。


每个插线板有三根导线,编号 分别表示火线、零线、地线。在电路模型中,对每一对父子插线板,子插线板的任意一根线与父插线板的任意一根线之间均有一个电阻。因此每对父子之间有 个电阻。例如下图中, 和 的父亲都是 。

这些电阻的大小会随时间改变。请在每次查询时,给出指定的两根导线之间的等效电阻。
输入格式
第一行一个正整数 ,表示插线板数。接下来 行按每四行一块给出父子关系和电路参数。第 块描述编号为 的插线板。
- 第一行给出父插线板的编号。
- 接下来三行,每行三个整数,构成矩阵 。第 行第 列的 是该子插线板第 根线和父插线板第 根线之间电阻的倒数。
接下来一行一个整数 ,表示操作数。随后 行,每行一种操作。
1 a x y g将插线板 的第 根线和它的父插线板的第 根线之间的电阻改为 ,保证 。2 a x b y查询插线板 的第 根线与插线板 的第 根线之间的等效电阻,保证 。
输出格式
每次查询输出一行实数。设标准答案为 ,输出值为 ,正确条件是
一个测试点的所有查询都正确,才可获得该点分数。
样例 #1
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
0.083836
0.095256
0.078828
0.146900
补充样例 #2
2
1
1 1 1
1 1 1
1 1 1
1
2 1 1 2 1
0.555555555556
两组各三根导线构成单位电导的完全二分图,指定两侧各一根导线之间的等效电阻为 。
数据范围
父子关系构成一棵树。导线编号均为 。初始电阻与修改后的电阻,其倒数均为不大于 的正整数。
| 原赛测试点 | 上限 | 上限 | 其他约定 |
|---|---|---|---|
| 1–6 | 100 | 1000 | 只有查询 |
| 7–10 | 1000 | 树为一条链 | |
| 11–16 | 10000 | 树的高度不超过 30 | |
| 17–20 | 无 | ||