CTSC2012 电阻网络

在各学科交叉应用的潮流下，一道具有超前预见性的好题。

Solution

前置知识

欧姆定律

在同一电路中，通过某段导体的电流跟这段导体两端的电压成正比，跟这段导体的电阻成反比。

\[I=\frac{U}{R}\]

其中 \(I\) 为电流，\(U\) 为电压，\(R\) 为电阻。

基尔霍夫第一定律

会合于任意节点的电流和等于零。

\[\sum I=0\]

Solution

本题中全部为相同电阻，所以答案与电阻大小无关，记电阻大小为 \(R\)，钦定一个叶子节点为根。

考虑第 \(i\) 个节点，记 \(i\) 的父亲为 \(fa\)，儿子集合为 \(son\)，\(fa\rightarrow i\) 的电流为 \(I_i\)。

则从 \(fa\) 到 \(i\) 的过程中，电势差的产生可以看作两部分，一部分是电阻导致的电势的下降，一部分是电源导致的电势的上升，这两部分之和等于电势差。即：

\[\varphi_i=\varphi_{fa}-I_iR+E_i\]

移项得：

\[I_i=\frac{\varphi_{fa}-\varphi_i+E_i}{R}\]

这是 \(i\) 祖先方向的电流，同理，对于儿子方向的任意 \(x\in son\)，我们有：

\[\varphi_x=\varphi_{i}-I_xR+E_x\]

得：

\[I_x=\frac{\varphi_{i}-\varphi_x+E_x}{R}\]

求和得：

\[\sum\limits_{x\in son}I_x=\sum\limits_{x\in son}\frac{\varphi_{i}-\varphi_x+E_x}{R}\]

根据基尔霍夫第一定律：

\[I_i=\sum\limits_{x\in son}I_x\]

即：

\[\frac{\varphi_{fa}-\varphi_i+E_i}{R}=\sum\limits_{x\in son}\frac{\varphi_{i}-\varphi_x+E_x}{R}\]

继续化简：

\[\varphi_{fa}-\varphi_i+E_i=\sum\limits_{x\in son}(\varphi_{i}-\varphi_x+E_x)\]

\[\varphi_{fa}-\varphi_i+E_i=|son|\varphi_i-\sum\limits_{x\in son}(\varphi_x-E_x)\]

\[(|son|+1)\varphi_i=\varphi_{fa}+E_i+\sum\limits_{x\in son}(\varphi_x-E_x)\]

注意到 \(|son|\) 是儿子集合，相当于当前节点向儿子方向的度数；\(1\) 相当于当前节点向父亲方向的度数，所以 \(|son|+1\) 实际上相当于节点 \(i\) 的度数，记为 \(\deg_i\)。

\[\deg_i\varphi_i=\varphi_{fa}+E_i+\sum\limits_{x\in son}(\varphi_x-E_x)\]

设 \(\varphi_i=K_i\varphi_{fa}+B_i\)，其中 \(K_i,B_i\) 都是只与 \(i\) 和 \(son\) 有关的常量。

把 \(\varphi_x\) 用刚刚的形式表示出来：

\[\varphi_x=K_x\varphi_{i}+B_x\]

代入原式：

\[\varphi_i=\frac{\varphi_{fa}+E_i+\sum\limits_{x\in son}(K_x\varphi_{i}+B_x-E_x)}{\deg_i}\]

把这个式子表示成刚刚的形式：

\[\deg_i\varphi_i=\varphi_{fa}+E_i+\sum\limits_{x\in son}(K_x\varphi_{i}+B_x-E_x)\]

\[\deg_i\varphi_i=\varphi_{fa}+E_i+\varphi_i\sum\limits_{x\in son}K_x+\sum\limits_{x\in son}(B_x-E_x)\]

\[\varphi_i(\deg_i-\sum\limits_{x\in son}K_x)=\varphi_{fa}+E_i+\sum\limits_{x\in son}(B_x-E_x)\]

\[\varphi_i=\frac{1}{\deg_i-\sum\limits_{x\in son}K_x}\varphi_{fa}+\frac{\sum\limits_{x\in son}(B_x-E_x)+E_i}{\deg_i-\sum\limits_{x\in son}K_x}\]

我们发现此时已经表示成 \(\varphi_i=K_i\varphi_{fa}+B_i\) 的形式了。那么：

\[K_i=\frac{1}{\deg_i-\sum\limits_{x\in son}K_x}\]

\[B_i=\frac{\sum\limits_{x\in son}(B_x-E_x)+E_i}{\deg_i-\sum\limits_{x\in son}K_x}=K_i(\sum\limits_{x\in son}(B_x-E_x)+E_i)\]

因为我们要求 \(i\) 到地面，所以特判一下叶子。叶子度数为 \(2\)，一条边连向地面，地面电势为 \(0\)。

Code

#include<bits/stdc++.h>
using namespace std;

const int MAXM = 1e5 + 7;
const int MAXN = 5e4 + 7;

struct Edge
{
    int to, nxt;
}edge[MAXM];

int head[MAXN], cnt;
int rt, n, m;
int deg[MAXN], fa[MAXN];
double k[MAXN], b[MAXN], sumb[MAXN], ph[MAXN], sumph[MAXN];

void add_edge(int u, int v)
{
    edge[++cnt] = (Edge){v, head[u]};
    head[u] = cnt;
    edge[++cnt] = (Edge){u, head[v]};
    head[v] = cnt;
}

void init(int u, int f)
{
    fa[u] = f;
    double sumk = 0;
    for(int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if(v != f)
        {
            init(v, u);
            sumk += k[v];
        }
    }
    k[u] = 1.0 / (deg[u] - sumk);
}

void add(int u, int e)
{
    if(u == 0) return;
    else
    {
        sumb[fa[u]] -= b[u];
        b[u] = (sumb[u] + sumph[u] - ph[u]) * k[u];
        sumb[fa[u]] += b[u];
        add(fa[u], e);
    }
}

void modify(int u, int v, int e)
{
    if(fa[v] == u)
    {
        swap(u, v);
        e = -e;
    }
    ph[u] -= e;
    sumph[v] -= e;
    add(u, e);
}

double query(int u)
{
    if(u == 0) return 0;
    return k[u] * query(fa[u]) + b[u];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        deg[u]++, deg[v]++;
    }
    for(int i = 1; i <= n; i++)
    {
        if(deg[i] == 1)
        {
            add_edge(i, 0);
            deg[0] = 1;
            break;
        }
    }
    for(int i = 1; i <= n; i++)
        if(deg[i] == 1) deg[i] = 2;
    init(0, 0);
    for(int i = 1; i <= m; i++)
    {
        char ch;
        cin >> ch;
        if(ch == 'Q')
        {
            int u;
            scanf("%d", &u);
            printf("%.10lf\n", query(u));
        }
        else
        {
            int u, v, e;
            scanf("%d%d%d", &u, &v, &e);
            modify(u, v, e);
        }
    }
    return 0;
}