#P4020. [CTSC2012] 电阻网络

    ID: 1016 远端评测题 4000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>递推高斯消元WC/CTSC/集训队2012Special Judge

[CTSC2012] 电阻网络

题目描述

给定一个树型电网,树中的每条边上有一个电阻RiR_i,电阻值均为10000Ω。下图为一个包含4个节点的树型电路情况:

图1

树中的所有叶子节点(度为1的节点称为叶子)都接地,每条线上都接地,每条线上都附有10000Ω的电阻,最终形成的电网如下图所示:

图2

现有如下两种操作:

C u v w:表示在边<u,v>上串联一个电源,电源的大小为ww伏,电源位于靠近节点uu一侧(如下图所示),电源负极指向uu。注意同一条边上可以串联多个电源。

图3

Q u :表示询问点uu当前的电压,此是指对地。

如对上图进行C 2 4 5操作后,网络变为:

图4

此时每个节点上的电压见上图的标注。

输入格式

输入文件 circuit.in 的第一行包含两个整数 N,MN,M,分别表示树的节点数和操作个数。接下来 N1N-1 行,每行两个数 u,vu,v,表示有一条连接节点 u,vu,v 的边,这条边上恰好包含一个电阻。

接下来 MM 行,每行一个命令,格式见题目描述。

输出格式

输出文件为 circuit.out。对于每个 Q 命令,输出一个数表示此刻该点的电压值。你可以输出任意多位的小数,只要你的答案和标准答案相差不超过 10^(-3) 就算合法。

4 3
1 2
2 3
2 4
Q 2
C 2 4 5
Q 2
0.0000000000
-1.6666666666

提示

【样例说明】

对于第一个询问,由于原图中没有电源,所以没有电流,所有点的电压都相

等(否则如果有 U i >U j ,则就有 i 流向 j 的电流,与没有电源矛盾),都等于地电

压 0V。

之后在<2,4>中加一个 5V 的电源,得到的新图见题目描述。

整理后可以发现,新图的形式是串联(电源,R 2 +10000,并联(R 1 +10000,

R 3 +10000)),由此可以得到新图的总电阻为:

R 2 +10000+1/(1/(R 3 +10000)+1/(R 1 +10000))=30000 Ω.

所以流过节点 4 的电流就是 5/30000A,所以 U 4 =5/3V。U 2 =U 4 +R 2 *I-5=-5/3V,由

于 U 1 和 U 3 形式对称,由分压关系可知 U 1 =U 3 =U 2 *10000/(10000+10000)=-5/6V。

【数据规模】

30%的数据保证 N,M ≤ 30

60%的数据保证 N,M ≤ 3000

100%的数据保证 3 ≤ N,M ≤ 50000,1 ≤ u,v ≤ n,1 ≤ w ≤ 10,树中最长链的长

度不超过 50。