标签：树形DP
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
分析：先默认一个根节点，计算初始的答案，然后每次O（1）计算出其儿子节点作为根节点的ans值，更新答案
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define LL long long
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
LL f[maxn],n,cnt=0,ans=0,head[maxn],deep[maxn],size[maxn];
struct edge{int to,next;}e[maxn<<1];
void dfs1(int x,int fa)
{
size[x]=1;
f[x]=deep[x];
reg(x)
if(e[i].to!=fa){
deep[e[i].to]=deep[x]+1;
dfs1(e[i].to,x);
f[x]+=f[e[i].to];
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int fa)
{
reg(x)
if(e[i].to!=fa)
{
f[e[i].to]=f[x]+n-2*size[e[i].to];
dfs2(e[i].to,x);
}
}
int main()
{
n=read();
rep(i,1,n-1){
int u=read(),v=read();
e[++cnt]=(edge){v,head[u]};head[u]=cnt;
e[++cnt]=(edge){u,head[v]};head[v]=cnt;
}
dfs1(1,0);
dfs2(1,0);
rep(i,1,n)
if(f[i]>f[ans])ans=i;
printf("%lld\n",ans);
return 0;
}
