经典问题之树的深度

给定一棵树，求出分别以每个点为根的树的深度。

其实这道题是四五月份时宁波初中比赛时的题目，当时的数据范围自然是１０００，然后Ｏ（ｎ＾２）水过。当时比赛时题做完了，闲的无聊，打算想一想Ｏ（ｎ）做法，当时也感觉挺可做的。几个月后突然想起来，今天就写了一下。算是一道树形ｄｐ吧。

这题描述简单，做法也算有趣，自己感觉是个有意思的问题。

解答也一句话，意会即可：

每个点的深度＝ＭＡＸ（每个点向下的最长路，每个点向上的最长路）；

每个点向下的最长路＝ＭＡＸ（子树的向下的最长路）＋１；

每个点向上的最长路＝ＭＡＸ（父亲向上的最长路＋１，父亲向下的次长路＋１）【当这个点是父亲最大的儿子时】，

父亲的深度＋１【当这个点不是父亲最大的儿子时】。

我们还可以有一些好的拓展。

请看下面一道题

树的合并(connect.pas/c/cpp)
给定两棵树，则总共有N*M 种方案把这两棵树通过加一条边连成一棵树，求这N*M 棵
树的直径大小之和。
N<=10^5,M<=10^5

可以用预处理+排序+扫描的方法在O(NlogN)时间内解决。具体见Code。

connect

  1 /*
  2     Problem:
  3     Algorithm:
  4     Note:
  5 */
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<set>
 10 #include<vector>
 11 #include<map>
 12 #include<string>
 13 #include<iomanip>
 14 #include<iostream>
 15 #include<cmath>
 16 #include<queue>
 17 using namespace std;
 18 
 19 #define rep(i,x,y) for(i=x;i<=y;i++)
 20 #define _rep(i,x,y) for(i=x;i>=y;i--)
 21 #define CL(S,x) memset(S,x,sizeof(S))
 22 #define CP(S1,S2) memcpy(S1,S2,sizeof(S2))
 23 #define mp make_pair
 24 //#define x first
 25 //#define y second
 26 #define MAX(x,y) ((x)>(y)?(x):(y))
 27 //#define MIN(x,y) ((x)<(y)?(x):(y))
 28 #define sqr(x) ((x)*(x))
 29 
 30 typedef long long int64;
 31 typedef long double real;
 32 
 33 const int MAXN=200010;
 34 int N[2],i,j,best;int64 ans0;
 35 int st[2][MAXN],q[MAXN],fa[MAXN];
 36 int ans[MAXN],dep[MAXN],up[MAXN],maxson0[MAXN],maxson1[MAXN];
 37 int64 sum[MAXN];
 38 
 39 struct E
 40 {
 41     int edge,e[MAXN],b[MAXN],first[MAXN],last[MAXN];
 42     void clear(){CL(first,-1);CL(b,-1);}
 43     void add(int x,int y)
 44     {
 45         e[edge]=y;
 46         if(first[x]==-1)first[x]=edge;
 47         else b[last[x]]=edge;
 48         last[x]=edge++;
 49     }
 50 }g[2];
 51 
 52 int bfs(int start,int t)
 53 {
 54     int i,j,k;
 55     q[1]=start;CL(fa,0);
 56     for(i=j=1;i<=j;i++)
 57     for(k=g[t].first[q[i]];k>=0;k=g[t].b[k])
 58     if(g[t].e[k]!=fa[q[i]]){fa[g[t].e[k]]=q[i];q[++j]=g[t].e[k];}
 59     return q[j];
 60 }
 61 void work(int t)
 62 {
 63     int i,j,k,n=N[t];
 64     bfs(1,t);CL(dep,0);CL(maxson0,0);CL(maxson1,0);
 65     ans[0]=dep[0]=-1;
 66     _rep(i,n,1)
 67     {
 68         for(k=g[t].first[q[i]];k>=0;k=g[t].b[k])
 69         if(g[t].e[k]!=fa[q[i]])
 70         if(dep[g[t].e[k]]>dep[maxson0[q[i]]])maxson1[q[i]]=maxson0[q[i]],maxson0[q[i]]=g[t].e[k];
 71         else if(dep[g[t].e[k]]>dep[maxson1[q[i]]])maxson1[q[i]]=g[t].e[k];
 72         dep[q[i]]=dep[maxson0[q[i]]]+1;
 73     }
 74 
 75     rep(i,1,n)
 76     {
 77         if(q[i]!=maxson0[fa[q[i]]])up[q[i]]=ans[fa[q[i]]]+1;
 78         else up[q[i]]=MAX(up[fa[q[i]]]+1,dep[maxson1[fa[q[i]]]]+2);
 79         ans[q[i]]=MAX(up[q[i]],dep[q[i]]);
 80     }
 81     
 82     st[t][0]=n;
 83     rep(i,1,n)st[t][i]=ans[i];
 84     
 85 }
 86 
 87 int main()
 88 {
 89     freopen("connect.in","r",stdin);
 90     freopen("connect.out","w",stdout);
 91     scanf("%d%d",&N[0],&N[1]);
 92     g[0].clear();g[1].clear();
 93     int x,y;
 94     rep(i,1,N[0]-1)scanf("%d%d",&x,&y),g[0].add(x,y),g[0].add(y,x);
 95     rep(i,1,N[1]-1)scanf("%d%d",&x,&y),g[1].add(x,y),g[1].add(y,x);
 96     
 97 
 98     work(0);work(1);
 99     
100     
101     sort(st[0]+1,st[0]+1+st[0][0]);
102     sort(st[1]+1,st[1]+1+st[1][0]);
103     
104     best=MAX(st[0][st[0][0]],st[1][st[1][0]]);
105     
106     _rep(i,st[1][0],1)sum[i]=sum[i+1]+st[1][i];
107     st[1][st[1][0]+1]=MAXN*10;
108     
109     for(i=1,j=st[1][0];i<=st[0][0];i++)
110     {
111         while(j&&st[0][i]+st[1][j]+1>=best)j--;j++;
112         ans0+=sum[j]+int64(st[0][i]+1)*(st[1][0]-j+1)+int64(best)*(j-1);
113     }
114     cout<<ans0<<endl;
115     scanf("\n");
116     return 0;
117 }