首页 > 代码库 > BZOJ 3727 DP?推式子..
BZOJ 3727 DP?推式子..
思路:
设$sum[i]表示i的子树中a[i]的和$
$b[1]=\Sigma a[i]*dis[i] = \Sigma _{i=2} ^n sum[i]$
$b[x]-b[fa[x]]=sum[1]-2*sum[x]$
$sum[1]={\Sigma_{i=2}^n (b[x]-b[fa[x]])+2*b[1] \over n-1}$
$求出sum[1]以后根据a[x]=sum[x]-\Sigma_{v是x的儿子} sum[v]带入求出其它值即可$
$复杂度O(n)$
//By SiriusRen#include <cstdio>#include <cstring>using namespace std;#define int long longconst int N=600500;int n,xx,yy,first[N],next[N],v[N],tot,fa[N],rev[N],cnt,b[N],X;long long sum[N],ans[N];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){ rev[++cnt]=x; for(int i=first[x];~i;i=next[i])if(v[i]!=fa[x]) fa[v[i]]=x,dfs(v[i]);}void dfs2(int x){ ans[x]=sum[x]; for(int i=first[x];~i;i=next[i])if(v[i]!=fa[x]) dfs2(v[i]),ans[x]-=sum[v[i]];}signed main(){ memset(first,-1,sizeof(first)); scanf("%lld",&n); for(int i=1;i<n;i++)scanf("%lld%lld",&xx,&yy),add(xx,yy),add(yy,xx); for(int i=1;i<=n;i++)scanf("%lld",&b[i]); dfs(1); for(int i=2;i<=n;i++)sum[1]+=(b[i]-b[fa[i]]); sum[1]=(sum[1]+2*b[1])/(n-1); for(int i=2;i<=n;i++)X=rev[i],sum[X]=(sum[1]-b[X]+b[fa[X]])/2; dfs2(1); for(int i=1;i<=n;i++)printf("%lld%c",ans[i],i!=n?‘ ‘:‘\n‘);}
BZOJ 3727 DP?推式子..
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。