#P3556. [Ctsc2014] 插线板

    ID: 2674 传统题 4000ms 256MiB 尝试: 31 已通过: 7 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS动态规划树链剖分维护 DP数据结构普通线段树线性代数与代数行列式矩阵求逆矩阵乘法Schur 补Cholesky 分解CF3300

[Ctsc2014] 插线板

[CTSC2014] 插线板

题目描述

Allison 有许多要充电的电子设备,她为此购买了 nn 个插线板。她家里只有一个插座。除了接到这个插座的根插线板,其余每个插线板都接到另一个插线板上,构成一棵树。根插线板的编号为 11。

原题中的插线板

多个插线板的树形连接

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

两个子插线板的每根导线都通过电阻连接到父插线板的三根导线

这些电阻的大小会随时间改变。请在每次查询时,给出指定的两根导线之间的等效电阻。

输入格式

第一行一个正整数 nn,表示插线板数。接下来 4(n−1)4(n-1) 行按每四行一块给出父子关系和电路参数。第 ii 块描述编号为 i+1i+1 的插线板。

  • 第一行给出父插线板的编号。
  • 接下来三行,每行三个整数,构成矩阵 gg。第 xx 行第 yy 列的 gxyg_{xy} 是该子插线板第 xx 根线和父插线板第 yy 根线之间电阻的倒数。

接下来一行一个整数 qq,表示操作数。随后 qq 行,每行一种操作。

  • 1 a x y g 将插线板 aa 的第 xx 根线和它的父插线板的第 yy 根线之间的电阻改为 1/g1/g,保证 2≤a≤n2\le a\le n。
  • 2 a x b y 查询插线板 aa 的第 xx 根线与插线板 bb 的第 yy 根线之间的等效电阻,保证 a≠ba\ne b。

输出格式

每次查询输出一行实数。设标准答案为 RR,输出值为 R^\widehat R,正确条件是

∣R^−RR∣<10−3.\left|\frac{\widehat R-R}{R}\right|<10^{-3}.

一个测试点的所有查询都正确,才可获得该点分数。

样例 #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

两组各三根导线构成单位电导的完全二分图,指定两侧各一根导线之间的等效电阻为 5/95/9。

数据范围

父子关系构成一棵树。导线编号均为 1,2,31,2,3。初始电阻与修改后的电阻,其倒数均为不大于 1010 的正整数。

原赛测试点 nn 上限 qq 上限 其他约定
1–6 100 1000 只有查询
7–10 1000 树为一条链
11–16 10000 树的高度不超过 30
17–20 无