【BZOJ 3727】 3727: PA2014 Final Zadanie （递推）

3727: PA2014 Final Zadanie

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 279 Solved: 121

Description

吉丽YY了一道神题，题面是这样的：
“一棵n个点的树，每条边长度为1，第i个结点居住着a[i]个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为b[i]。输出所有b[i]。”
吉丽已经造好了数据，但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗？

Input

第一行一个整数n(2<=n<=300000)。
接下来n-1行，每行两个整数x,y，表示x和y之间有连边。
接下来一行由空格隔开的n个整数b[i](0<=b[i]<=10^9)。

Output

输出一行由空格隔开的n个整数a[i]。
如果你觉得有多组解就任意输出其中一组。

Sample Input

2
1 2
17 31

Sample Output

31 17

HINT

Source

鸣谢Jcvb

【分析】

　　高斯消元肯定是不行的。

　　直接计算肯定是不行的。

　　output那个多解那句话一脸嘲讽肯定是唯一解的。

　　好了，肯定是和父亲差分，这样的式子才靠谱。

　　有：b[fa[i]]-b[i]=sum[i]-(tot-sum[i])=2*sum[i]-tot

　　tot是全树的a的和，你把1当成根的话就是sum[1]。

　　这时候，大家都想把tot求出来。

　　tot=b[fa[i]]-b[i]-2*sum[i]

　　肯定是要加起来的。

　　$(n-1)*tot=\sum_{i=1}^{n-1} b[fa[i]]-b[i] -2*sum[i]$

　　但是有sum[i]不知道的怎么破。。。聪明的别人看出来他们的和就是b[1]啊。

　　就可以求tot了，有tot就可以求sum了，就可以求a了。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 300010

 #define LL long long

 struct node

 {

     int x,y,next;

 }t[Maxn*];

 int len,first[Maxn];

 int fa[Maxn];

 LL sum[Maxn],a[Maxn],b[Maxn];

 void ins(int x,int y)

 {

     t[++len].x=x;t[len].y=y;

     t[len].next=first[x];first[x]=len;

 }

 void dfs(int x,int f)

 {

     fa[x]=f;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)

     {

         dfs(t[i].y,x);

     }

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     len=;

     memset(first,,sizeof(first));

     for(int i=;i<n;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         ins(x,y);ins(y,x);

     }

     for(int i=;i<=n;i++) scanf("%lld",&b[i]);

     dfs(,);

     LL sm=;

     for(int i=;i<=n;i++) sm+=b[i]-b[fa[i]];

     sm+=*b[];

     sm/=(n-);sum[]=sm;

     for(int i=;i<=n;i++) sum[i]=(b[fa[i]]-b[i]+sm)/;

     for(int i=;i<=n;i++) a[i]=sum[i];

     for(int i=;i<=n;i++) a[fa[i]]-=sum[i];

     for(int i=;i<n;i++) printf("%lld ",a[i]);printf("%d\n",a[n]);

     return ;

 }

LONG LONG

2017-04-08 09:47:14

巴特西

【BZOJ 3727】 3727: PA2014 Final Zadanie （递推）

3727: PA2014 Final Zadanie

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章