题目链接： https://vijos.org/d/newbzoj/p/590c9893d3d8a132109937a3

其实题意很简单，先看一下：给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

如果暴力的话必然是会TLE的。

所以我们必须想办法。

我记得有一道题是把n次DFS优化为了2次DFS

这道题是不是也可以呢？

我们可以想想。

答案是可以的。

看一下思路：

首先所有点等于父树的点+子树的点。

那么只要求出这两者累加就好了；

子树的总深度简直好求，就是将儿子的总深度+size就好了；

父树的稍微有点麻烦，因为需要一些预处理所以在第二次深搜解决；

对于一个点来说，这个点的父树就是【父亲+父亲的父树+兄弟的子树】；

那么分别累加即可：
注意一下推公式就好；

时间复杂度O(n)
不过有几个细节问题：

1.公式 一定要算好(加减同一项不要消下去。。不然没法调。。)

2.此题需要long long 

后面是代码。

加了一些注释。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 const int maxn=1000005;
 6 using namespace std;
 7 typedef long long ll;
 8 int n,no,to[maxn<<1],next[maxn<<1],head[maxn],cnt;
 9 ll sum[maxn],size[maxn],fas[maxn],ans;
10 void add(int x,int y){
11     to[++cnt]=y;next[cnt]=head[x];head[x]=cnt;
12 }
13 void DFS1(int x,int pre){
14     size[x]=1;int i,y;//size是子树的大小 ,包括x 
15     for(i=head[x];i;i=next[i]){
16         if((y=to[i])!=pre){
17             DFS1(y,x);
18             size[x]+=size[y];
19             sum[x]+=sum[y]+size[y];//sum是深度和，但是不包括x 
20         }
21     }
22 }
23 void DFS2(int x,int pre){
24     int i,y;
25     if(x!=1)fas[x]=fas[pre]+n-size[pre]+sum[pre]-sum[x]-size[x]+size[pre]-size[x]-1+1;
26     //fas[pre]+n-size[pre]是第一部分
27     //sum[pre]-sum[x]-size[x]+size[pre]-size[x]-1 是第二部分
28     //1 是第三部分 
29     //公式要好好理解 
30     if(ans<fas[x]+sum[x]){//fas是父树和 
31         ans=fas[x]+sum[x]; 
32         no=x;
33     }
34     else if(ans==fas[x]+sum[x])no=min(no,x);
35     for(i=head[x];i;i=next[i]){
36         if((y=to[i])!=pre){
37             DFS2(y,x);
38         }
39     }
40 }
41 int main(){
42     //freopen("a.in","r",stdin);
43     scanf("%d",&n);
44     for(int i=1;i<n;i++){
45         int x,y; scanf("%d%d",&x,&y);
46         add(x,y);add(y,x);
47     }
48     DFS1(1,0);DFS2(1,0);
49     printf("%d\n",no);
50     return 0;
51 }