题目描述
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
输入
给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.
输出
输出你所找到的点,如果具有多个解,请输出编号最小的那个.
样例输入
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
1 4
5 6
4 5
6 7
6 8
2 4
3 4
样例输出
7
先求出以一个点为根的深度之和，再向子节点转移，每次转移到的子树中所有点深度-1，其他点深度+1.
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
using namespace std;
int head[2000010];
int next[4000010];
int to[4000010];
long long dep[2000010];
long long size[2000010];
long long ans[2000010];
int tot;
int n;
int x,y;
long long sum;
int num;
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x,int fa)
{
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa)
{
dep[to[i]]=dep[x]+1;
dfs(to[i],x);
size[x]+=size[to[i]];
}
}
}
void dfs2(int x,int fa)
{
ans[1]+=dep[x];
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa)
{
dfs2(to[i],x);
}
}
}
void dfs3(int x,int fa)
{
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa)
{
ans[to[i]]=ans[x]-size[to[i]]+n-size[to[i]];
dfs3(to[i],x);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
{
size[i]=1;
}
dep[1]=0;
dfs(1,1);
dfs2(1,1);
dfs3(1,1);
sum=0;
for(int i=1;i<=n;i++)
{
if(sum<ans[i])
{
sum=ans[i];
num=i;
}
}
printf("%d",num);
}