题意
给出一棵树，求一组 (a_i)， 满足：
[Large operatorname{dist(1,1)} imes a_1+operatorname{dist(1,2)} imes a_2+dotsoperatorname{dist(1,n)} imes a_n=b_1\Large operatorname{dist(2,1)} imes a_1+operatorname{dist(2,2)} imes a_2+dotsoperatorname{dist(2,n)} imes a_n=b_2\Large vdots\Large operatorname{dist(n,1)} imes a_1+operatorname{dist(n,2)} imes a_2+dotsoperatorname{dist(n,n)} imes a_n=b_n
]
题解
考虑算贡献 ？
设 (f_i) 表示第 (i) 个结点子树的 (a) 和。
(g_i) 表示第 (i) (dots) (f) 和
则 (Large f_1-2 imes f_i=b_i-b_{fa_i})
上面这个式子直接用图形理解应该会方便一点。
此外，
(Large b_1=g_1-f_1=sumlimits_{i=1}^n f_i-f_1=sumlimits_{i=2}^n f_i)
所以
(Large 2 imes b_1=2 imes sumlimits_{i=2}^nf_idots①)
因此
[Large sum_{i=1}^n f_1-2 imes f_i = sum_{i=1}^n b_i-b_{fa_i}
]
[Large n imes f_1-sum_{i=1}^n 2 imes f_i=sum b_i-sum b_{fa_i}
]
则：
[Large sum_{i=2}^n(b_i-b_{fa_i})=(n-1) imes f_1-sum_{i=2}^n2 imes f_i dots ②
]
所以：
[Large ①+②:sum_{i=2}^n(b_i-b_{fa_i})+2 imes b_1=(n-1) imes f_1
]
得到了：
[Large f_1=dfrac{2 imes b_1+sumlimits_{i=2}^n(b_i-b_{fa_i})}{n-1}
]
那么结合
[Large f_1-2 imes f_i=b_i-b_{fa_i}
]
，就可以求到每一个 (f_i) 了，然后再搜一遍得到 (a_i) 即可。
代码
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
vector <int> G[300005];
ll a[300005],f[300005],b[300005];
ll sum=0;
void dfs(int u,int fa,int op)
{
if(op==1&&fa) sum+=b[u]-b[fa];
else if(op==2&&fa) f[u]=(f[1]-b[u]+b[fa])/2,a[u]=f[u];
else if(op==2&&!fa) a[u]=f[1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs(v,u,op);
if(op==2) a[u]-=f[v];
}
}
int main() {
int n;
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)
{
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
sum+=2ll*b[1];
dfs(1,0,1);
f[1]=sum/(n-1);
dfs(1,0,2);
for(int i=1;i<=n;i++) printf("%lld ",a[i]);
return 0;
}