首页 > 代码库 > BZOJ 3727 Final Zadanie
BZOJ 3727 Final Zadanie
递推一下什么的就好了。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 300050 #define maxe 600050 using namespace std; long long n,x,y,g[maxv],nume=1,tot1=0,tot2=0,dis[maxv],b[maxv],sum[maxv]; long long fath[maxv]; struct edge { long long v,nxt; }e[maxe]; void addedge(long long u,long long v) { e[++nume].v=v;e[nume].nxt=g[u]; g[u]=nume; } long long read() { char ch;long long data=http://www.mamicode.com/0; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data; } void dfs1(long long x) { if (x-1) tot2+=(b[fath[x]]-b[x]); for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if (v!=fath[x]) { fath[v]=x;dis[v]=dis[x]+1; dfs1(v); } } } void dfs2(long long x) { for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if (v!=fath[x]) {sum[x]-=sum[v];dfs2(v);} } } int main() { n=read(); for (long long i=1;i<=n-1;i++) { x=read();y=read(); addedge(x,y);addedge(y,x); } for (int i=1;i<=n;i++) scanf("%lld",&b[i]); dfs1(1); sum[1]=(2*b[1]-tot2)/(n-1);for (long long i=2;i<=n;i++) sum[i]=(sum[1]+b[fath[i]]-b[i])/2; dfs2(1); for (long long i=1;i<=n-1;i++) printf("%lld ",sum[i]); printf("%lld\n",sum[n]); return 0; }
BZOJ 3727 Final Zadanie
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。