还记得小时候经常看少儿频道，“智慧树下你和我，智慧树下欢乐多，智慧树下做游戏，欢乐多又多”，长大后智慧树也没放过我；
zzy今天来到的智慧树下摘果子，智慧树很生气所以他想惩罚zzy，他就让树上的果子全部砸到zzy的头上。这棵树就是一个树形结构，每个节点有一颗果子。zzy想被砸的最轻，所以他可以选择一个节点为根，使得以这个点为根的树,所有点的深度之和最大。(这样果子离他的头就近了)。
Input
输入包含一个数字N,代表有N个点.N<=1000000 下面N-1条边.
Output
输出zzy找到的点,如果具有多个解,请输出编号最小的那个.
Sample InputCopy
81 45 64 56 76 82 43 4
Sample Output Copy
7
题意：一棵n个节点的树，找出一个点，使得以这个点为根时，所有点的深度之和最大（如果最大值相同，输出拥有更小编号的点 ）。
建树我建议用vector，虽然我用的还不是很熟练，但我觉得是真的好用，我看很多博主用的都是结构体，感觉写出来代码有点乱，初学者很容易搞蒙，比如说我；然后遍历每一个节点，方程呢就是a[kk]=a[x]+(n-2*siz[kk]);
注意建树是先每层一个到最后一个，然后再返回的；
代码：
#include<stdio.h>#include<stdlib.h>#include<iostream>#include<algorithm>#include<math.h>#include<string.h>#include<queue>#include<vector>using namespace std;int siz[1000010];//节点个数int dp[1000010];//深度int n;int a[1000010];vector<vector<int> >f(1000010);void dfs(int x,int fa)//建树{siz[x]=1;for(int i=0;i<f[x].size();i++){int kk = f[x][i];if(kk==fa)continue;dp[kk]=dp[x]+1;dfs(kk,x);siz[x]+=siz[kk];}}void ddfs(int x,int fa)//遍历每一个结点{for(int i=0;i<f[x].size();i++){int kk=f[x][i];if(kk==fa)continue;a[kk]=a[x]+(n-2*siz[kk]);///kk这个结点的最大深度和ddfs(kk,x);}return ;}int main(){while(~scanf("%d",&n)){int ans =0;for (int i=1;i<=n;i++)f[i].clear();for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);f[y].push_back(x);f[x].push_back(y);}dfs(1,0);ddfs(1,0);a[1]=1;for(int i=2;i<=n;i++){if(a[ans]<a[i])ans=i;}printf("%d\n",ans);}return 0;}
