题解：P3617 电阻网络

· · 题解

我们记 solve(s,t) 为电路 s 到 t 的电阻。

根据题目性质，每个点最多两条出边，分别到 l 和 r 两点，边权记做 w1 和 w2。对于当前的点 s，分情况讨论：

若不存在 r，即只有一条边，电阻为 w1+solve(l, t)

若存在 r，记 L 为从 s 出去的 2 条路径的汇合点，电阻为：

solve(s,t) = \frac{1}{\dfrac{1}{solve(l,L) + w1} + \dfrac{1}{solve(r,L) + w2}} + solve(L,t)

很显然，求 L 可以用倍增实现。