http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1345. 电阻网络
时间限制:5.0s   内存限制:256.0MB   Special Judge
总提交次数:18   AC次数:11   平均分:73.89
将本题分享到:
   
 
问题描述
  给定一个树型电网,树中的每条边上有一个电阻Ri,电阻值均为10000Ω。下图为一个包含4个节点的树型电路情况:


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


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


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

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


  此时每个节点上的电压见上图的标注。
输入格式
  输入第一行包含两个整数N,M,分别表示树的节点数和操作个数。接下来N-1行,每行两个数u,v,表示有一条连接节点u,v的边,这条边上恰好包含一个电阻。
  接下来M行,每行一个命令,格式见题目描述。
输出格式
  对于每个Q命令,输出一个数表示此刻该点的电压值。你可以输出任意多位的小数,只要你的答案和标准答案相差不超过10-3就算合法。


样例输入
4 3
1 2
2 3
2 4
Q 2
C 2 4 5
Q 2
样例输出
0.0000000000
-1.6666666666
样例说明
  对于第一个询问,由于原图中没有电源,所以没有电流,所有点的电压都相等(否则如果有Ui>Uj,则就有i流向j的电流,与没有电源矛盾),都等于地电压0V。
  之后在<2,4>中加一个5V的电源,得到的新图见题目描述。
  整理后可以发现,新图的形式是串联(电源,R2+10000,并联(R1+10000, R3+10000)),由此可以得到新图的总电阻为:
  R2+10000+1/(1/(R3+10000)+1/(R1+10000))=30000 Ω.
  所以流过节点4的电流就是5/30000A,所以U4=5/3V。U2=U4+R2*I-5=-5/3V,由于U1U3形式对称,由分压关系可知U1=U3=U2*10000/(10000+10000)=-5/6V。
数据规模和约定
  30%的数据保证N,M ≤ 30
  60%的数据保证N,M ≤ 3000
  100%的数据保证3 ≤ N,M ≤ 50000,1 ≤ u,vn,1 ≤ w ≤ 10,树中最长链的长度不超过50。