首页 > 代码库 > BZOJ 1131: [POI2008]Sta

BZOJ 1131: [POI2008]Sta

Description

一棵树,问以那个节点为根时根的总和最大.

Sol

DFS+树形DP.

第一遍统计一下 size 和 d.

第二遍转移根,统计答案就行了.

Code

/**************************************************************    Problem: 1131    User: BeiYu    Language: C++    Result: Accepted    Time:8028 ms    Memory:78700 kb****************************************************************/ #include <cstdio>#include <vector>#include <iostream>using namespace std; typedef long long LL;const int N = 1000005; int n;int s[N],d[N];LL sd[N];LL ans1,ans2;int nxt[N<<1],gto[N<<1],e,h[N]; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar();    while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } void Add_Edge(int fr,int to){ nxt[++e]=h[fr],gto[e]=to,h[fr]=e; } void DFS1(int u=1,int fa=0) {    s[u]=1,sd[u]=d[u]=d[fa]+1;    for(int i=h[u],v;i;i=nxt[i]) if((v=gto[i])!=fa) {        DFS1(v,u),s[u]+=s[v],sd[u]+=sd[v];    }}void DFS2(int u=1,int fa=1,LL x=0) {    LL res=x+(sd[u]-(LL)d[u]*s[u]);//  cout<<u<<" "<<res<<endl;    if(ans2<res || (ans2==res && ans1>u)) ans1=u,ans2=res;    for(int i=h[u],v;i;i=nxt[i]) if((v=gto[i])!=fa) {        DFS2(v,u,x+n-s[v]+(sd[u]-sd[v])-(LL)d[u]*(s[u]-s[v]));      }} int main(){//  freopen("in.in","r",stdin);         n=in();    for(int i=1,u,v;i<n;i++) u=in(),v=in(),Add_Edge(u,v),Add_Edge(v,u);         d[0]=-1;    DFS1();    ans1=1,ans2=sd[1];    DFS2();    cout<<ans1<<endl;         return 0;}

  

BZOJ 1131: [POI2008]Sta