首页 > 代码库 > 【BZOJ 3727】 3727: PA2014 Final Zadanie (递推)
【BZOJ 3727】 3727: PA2014 Final Zadanie (递推)
3727: PA2014 Final Zadanie
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 279 Solved: 121Description
吉丽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 31Sample Output
31 17HINT
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了。。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 300010 8 #define LL long long 9 10 struct node 11 { 12 int x,y,next; 13 }t[Maxn*2]; 14 int len,first[Maxn]; 15 int fa[Maxn]; 16 LL sum[Maxn],a[Maxn],b[Maxn]; 17 18 void ins(int x,int y) 19 { 20 t[++len].x=x;t[len].y=y; 21 t[len].next=first[x];first[x]=len; 22 } 23 24 void dfs(int x,int f) 25 { 26 fa[x]=f; 27 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f) 28 { 29 dfs(t[i].y,x); 30 } 31 } 32 33 int main() 34 { 35 int n; 36 scanf("%d",&n); 37 len=0; 38 memset(first,0,sizeof(first)); 39 for(int i=1;i<n;i++) 40 { 41 int x,y; 42 scanf("%d%d",&x,&y); 43 ins(x,y);ins(y,x); 44 } 45 for(int i=1;i<=n;i++) scanf("%lld",&b[i]); 46 dfs(1,0); 47 LL sm=0; 48 for(int i=2;i<=n;i++) sm+=b[i]-b[fa[i]]; 49 sm+=2*b[1]; 50 sm/=(n-1);sum[1]=sm; 51 for(int i=2;i<=n;i++) sum[i]=(b[fa[i]]-b[i]+sm)/2; 52 for(int i=1;i<=n;i++) a[i]=sum[i]; 53 for(int i=2;i<=n;i++) a[fa[i]]-=sum[i]; 54 for(int i=1;i<n;i++) printf("%lld ",a[i]);printf("%d\n",a[n]); 55 return 0; 56 }
LONG LONG
2017-04-08 09:47:14
【BZOJ 3727】 3727: PA2014 Final Zadanie (递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。