[文章目录]
Description
“一棵n个点的树，每条边长度为1，第i个结点居住着a[i]个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为b[i]。输出所有b[i]。”吉丽已经造好了数据，但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗？2<=n<=300000 0<=b[i]<=10^9
正推式子的方程：设siz[x]表示x子树的a[i]的和。y为x的儿子,整个树的根为rot
b[y]=b[x]+siz[rot]-2*siz[y]
发现方程只有n-1个，而未知的siz有n个。。。
考虑根：b[rot]=作为第n个方程。
得
之后就随便了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 301000
using namespace std;
typedef long long ll;
int n;
int b[N],head[N],to[N<<1],nxt[N<<1],fa[N],cnt;
ll sum,s[N];
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x)
{
for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa[x])
{
fa[to[i]]=x;
dfs(to[i]);
}
}
void dfs1(int x)
{
for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa[x])
{
s[to[i]]=(sum+b[x]-b[to[i]])>>1;
dfs1(to[i]);
}
}
int main()
{
scanf("%d",&n); int x,y;
for(int i=1;i!=n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1;i<=n;++i) scanf("%d",b+i);
dfs(1); sum=b[1]<<1;
for(int i=2;i<=n;++i) sum+=b[i]-b[fa[i]];
sum/=(n-1); s[1]=sum;
dfs1(1); ll a;
for(int i=1;i<=n;++i)
{
a=s[i];
for(int j=head[i];j;j=nxt[j]) if(to[j]!=fa[i]) a-=s[to[j]];
printf("%lld%c",a,(i==n)?'\n':' ');
}
return 0;
}