题目:
Description
吉丽YY了一道神题，题面是这样的：
“一棵n个点的树，每条边长度为1，第i个结点居住着a[i]个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为b[i]。输出所有b[i]。”
吉丽已经造好了数据，但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗？
题解:
对于节点(u)设其父亲为(fa_u).子树的(a_i)之和为(sum_i)
设(SUM = sum_{u in G}a_u)
则对于任意的(u
eq 1)有:(b_u - b_{fa_u} = SUM - 2*sum_u)
且(b_1 = sum_{u
eq 1}sum_u)
然后我们将所有的(b_u - b_{fa_u} = SUM - 2*sum_u)求和
得:(sum (b_u - b_{fa_u}) = (n-1)*SUM - 2sum_{u
eq 1}sum_u)
我们将(b_1 = sum_{u
eq 1}sum_u)翻倍加上去有.
(2*b_1 = sum (b_u - b_{fa_u}) = (n-1)*SUM)
于是我们有:(SUM = frac{2*b_1 + sum_{u
eq 1}(b_u - b_{fa_u})}{n-1})
既然我们得到了SUM,那么将其代入到所有的(b_u - b_{fa_u} = SUM - 2*sum_u)中即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 300010;
int n;
struct Egde{
int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
int b[maxn],sum[maxn],fa[maxn],a[maxn];
#define v G[i].to
void dfs1(int u){
for(int i = head[u];i;i=G[i].next){
if(v == fa[u]) continue;
fa[v] = u;dfs1(v);
}
}
void dfs2(int u){
a[u] = sum[u];
for(int i = head[u];i;i=G[i].next){
if(v == fa[u]) continue;
dfs2(v);a[u] -= sum[v];
}
}
#undef v
inline void init(){
memset(head,0,sizeof head);
cnt = 0;
}
int main(){
init();read(n);
for(int i=1,u,v;i<n;++i){
read(u);read(v);
add(u,v);add(v,u);
}
memset(sum,0,sizeof sum);
memset(fa,0,sizeof fa);
for(int i=1;i<=n;++i) read(b[i]);
dfs1(1);
ll x = 0;
for(int i=2;i<=n;++i){
x += b[i] - b[fa[i]];
}x += 2LL*b[1];
ll SUM = x/(n-1);
sum[1] = SUM;
for(int i=2;i<=n;++i){
sum[i] = SUM - (b[i] - b[fa[i]]);
sum[i] >>= 1;
}
dfs2(1);
for(int i=1;i<=n;++i){
printf("%d",a[i]);
if(i != n) putchar(' ');
else putchar('
');
}
return 0;
}