标签：树形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;
}