首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。