自动搬运

查看原文

来自洛谷，原作者为

	SuperJvRuo **

搬运于2025-08-24 21:55:38，当前版本为作者最后更新于2018-10-28 12:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本篇题解符号约定：

物理量	符号
电流	I
电动势	E
电阻	R
电势差（电压）	U
电势	$\varphi$

这是一道电学题，我们复习一些电学内容：

1.欧姆定律

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

$$I=\frac{U}{R}$$

2.基尔霍夫第一定律

汇合于任一节点处的各电流的代数和等于0，即:

$$\sum I=\sum I_{in}+\sum I_{out}=0$$

对于一些电学题目，可以依据欧姆定律和基尔霍夫第一定律列出方程组，利用高斯消元求解。

但是这题数据范围50000，高斯消元只能获得30pts。我们注意到树上的最长链长度不超过50，应考虑由父亲到儿子或是儿子到父亲的递推关系，暴力递推答案。

显然，只要本题中所有的电阻器阻值相同，不论每个电阻的阻值是$10000\Omega$还是$0.1\Omega$，答案都是一样的。因此我将每个电阻的阻值记为$R$。为了便于计算，钦点一个叶子节点为根。

考虑节点$i$：

设$i$的父节点为$fa$，子节点集合为$son$，$fa$到$i$的电流为$I_i$。

由父节点$fa$到$i$的电路中，电阻处电势的下降，加上电源带来的电势上升，其结果就等于两点的电势差：

$$I_iR+E_i=\varphi_{fa}-\varphi_{i}$$

移项得：

$$I_i=\frac{\varphi_{fa}-\varphi_{i}-E_i}{R}$$

同理，由$i$到每个子节点$x$的电路中，都有：

$$I_xR+E_x=\varphi_{i}-\varphi_{x}$$

移项，对所有子节点求和得：

$$\sum_{x\in son}I_x=\sum_{x\in son}\frac{\varphi_{i}-\varphi_{x}-E_x}{R} $$

$i$点的基尔霍夫第一定律：

$$\sum_{x\in son}I_x=I_i$$

将已求得的两个$I$带入第三个式子：

$$\sum_{x\in son}\frac{\varphi_{i}-\varphi_{x}-E_x}{R}=\frac{\varphi_{fa}-\varphi_{i}-E_i}{R} $$

整理得：

$$\varphi_i=\frac{\varphi_{fa}-E_i+\sum_{x\in son}(\varphi_x+E_x)}{deg_i} $$

为了暴力递推，设$\varphi_i=K_i\varphi_{fa}+B_i$，其中$K_i$和$B_i$都是只与$i$与$son$有关的系数，将上式中的$\varphi_x$以这种形式表示，即得：

$$\varphi_i=\frac{\varphi_{fa}-E_i+\sum_{x\in son}(K_x\varphi_i+B_x+E_x)}{deg_i} $$

提出系数：

$$K_i=\frac{1}{deg_i-\sum_{x\in son}K_x}$$ $$B_i=\frac{\sum_{x\in son}(B_x+E_x)-E_i}{deg_i-\sum_{x\in son}K_x}=K_i(\sum_{x\in son}(B_x+E_x)-E_i) $$

豁然开朗了是不是？

诶不对啊，我们要求的是$i$到地面的电势差啊？我们还要思考一下接地节点的边界处理。

叶子节点$i$在原图中的度数为1，算上接地的一条边，度数为2。地面的电势为$0$。因此：

$$\varphi_i=\frac{\varphi_{fa}-E_i}{2}$$

故：

$$K_i=\frac{1}{2}$$ $$B_i=\frac{-E_i}{2}$$

这样，我们求得的$\varphi_i$就是$i$点到地面的电势差了。

$K$与电路中的电源无关，可以预处理直接求。加电源的时候暴力向上修改$B$即可。查询电势差的时候也是向上dark♂力扫一遍。由于链长不超过50，其复杂度完全正确。

#include<cstdio>
#include<cctype>
#include<algorithm>

struct Edge
{
    int to,next;
}edge[100005];
int head[50005],cnt;

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;
}

int root;

int degree[50005],fa[50005];

double k[50005],b[50005],sum_b[50005],U[50005],sum_u[50005];

void init_k(int u,int f)
{
    fa[u]=f;
    double sum_k=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=f)
        {
            init_k(v,u);
            sum_k+=k[v];
        }
    }
    k[u]=1.0/(degree[u]-sum_k);
}

void Add_b(int u,int e)
{
    if(u==0)
        return;
    else
    {
        sum_b[fa[u]]-=b[u];
        b[u]=(sum_b[u]+sum_u[u]-U[u])*k[u];
        sum_b[fa[u]]+=b[u];
        Add_b(fa[u],e);
    }
}

void Modify(int u,int v,int e)
{
    if(fa[v]==u)
    {
        std::swap(u,v);
        e=-e;
    }
    U[u]+=e;
    sum_u[v]+=e;
    Add_b(u,e);
}

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

int main()
{
    int n,m,u,v,e;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        Add_edge(u,v);
        ++degree[u];
        ++degree[v];
    }
    
    for(int i=1;i<=n;++i)
    {
        if(degree[i]==1)
        {
            Add_edge(i,0);
            degree[0]=1;
            break;
        }
    }
    for(int i=1;i<=n;++i)
    {
        if(degree[i]==1)
            degree[i]=2;
    }
    init_k(0,0);
    
    while(m--)
    {
        char ch=getchar();
        while(!isalpha(ch))
        {
            ch=getchar();
        }
        if(ch=='Q')
        {
            scanf("%d",&u);
            printf("%.12lf\n",Query(u));
        }
        else
        {
            scanf("%d%d%d",&u,&v,&e);
            Modify(u,v,e);
        }
    }
    return 0;
}