BZOJ1131 POI2008 Sta
Description
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
Input
给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.
Output
输出你所找到的点,如果具有多个解,请输出编号最小的那个.
Sample Input
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
Sample Output
7
换根dp
第一次dfs记录一下以当前节点为根在原树中子树的dep值之和
第二次直接套路换根
开LL
别用vector存边
#include<bits/stdc++.h>
using namespace std;
#define N 1000000+10
#define LL long long
struct Edge{int v,next;}E[N<<1];
LL dep[N],f[N],g[N],siz[N],maxv=0;
int head[N],tot=0;
int ans,n;
void add(int u,int v){
E[++tot]=(Edge){v,head[u]};
head[u]=tot;
}
void dfs(int u,int fa){
f[u]=0;siz[u]=1;
siz[u]=1;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa)continue;
dfs(v,u);
f[u]+=f[v];
siz[u]+=siz[v];
}
f[u]+=siz[u];
}
void dfs2(int u,int fa){
LL tmp=g[u]+f[u];
if(tmp>maxv)maxv=tmp,ans=u;
else if(tmp==maxv)ans=min(ans,u);
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa)continue;
g[v]=g[u]+f[u]-f[v]-siz[v]+n-siz[v];
dfs2(v,u);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,0);
dfs2(1,0);
printf("%d",ans);
return 0;
}