树的直径

定义

树的直径——就是树中距离最大的两点的距离。

无根树直径的求法

求无根树的直径：

1.利用dp实现，就是求最长链与次长链，可以用两次DFS求得，这里就不详细讨论。

2.利用直径的性质：Step 1.首先任取一点作为根，用DFS找出树中与它距离最远的点，记为点k。

　　　　　　　　 Step 2.以k为根，再次DFS，找出树中与它距离最远的点，其距离即为直径。

有何理由？详见这里。

模版题

下面列出两题：

1.poj1985

非常裸，就是练练手。直接贴代码了。

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 struct node{
 5        int link,dt;
 6        node *next;
 7 }ES[90000],*son[40009];
 8 int m,n,t,s,ans,EC=0;
 9 void tr(int fa,int v,int d)
10 {
11      if (d>ans) ans=d,s=v;
12      for (node *tmp=son[v];tmp;tmp=tmp->next)
13          if (tmp->link!=fa){
14             int u=tmp->link;
15             tr(v,u,d+tmp->dt);
16             }
17 }
18 void addedge(int x,int y,int z)
19 {
20      ES[++EC].next=son[x];
21      son[x]=ES+EC;
22      son[x]->link=y;
23      son[x]->dt=z;
24 }
25 int main()
26 {
27     freopen("poj1985.in","r",stdin);freopen("poj1985.out","w",stdout);
28     while (scanf("%d%d",&n,&m)!=EOF){
29           ans=0;
30           memset(son,0,sizeof(son));
31           EC=0;
32           for (int i=1;i<=m;++i){
33               int x,y,l;
34               scanf("%d%d%d ",&x,&y,&l);
35               char c;
36               scanf("%c",&c);
37               addedge(x,y,l);
38               addedge(y,x,l);
39               }
40           tr(0,1,0);
41           ans=0;
42           tr(0,s,0);
43           printf("%d\n",ans);
44           }
45     fclose(stdin);fclose(stdout);
46 }

2.hdu2196

事实上也是水题。但是要先了解树的直径的性质。

若(s,t)是一条直径，则树中任意一点到s,t的距离的最大值必定是其与树中离他最远的点的距离。

何以如此？

证明非常简单。如下：

记u为树中一点，(s,t)为直径。

假设能够找到一点v使得dis[u][v]>max(dis[u][s],dis[u][t])（不妨设dis[u][s]>dis[u][t]），则dis[u][v]+dis[u][s]>dis[u][s]+dis[u][t]>=dis[s][t]=直径。
矛盾，于是结论成立。

了解了这个性质，这题就很简单了。3遍bfs即可。

View Code

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 #include <memory>
 5 using namespace std;
 6 struct node{
 7        int link,dt;
 8        node *next;
 9 }ES[30009],*son[10009];
10 int n,dis[10009],temp[10009],EC=0;
11 bool b[10009];
12 queue<int> q;
13 void addedge(int x,int y,int z)
14 {
15      ES[++EC].next=son[x];
16      son[x]=ES+EC;
17      son[x]->link=y;
18      son[x]->dt=z;
19 }
20 int bfs(int k)
21 {
22      int Max=0;
23      memset(dis,0,sizeof(dis));
24      memset(b,0,sizeof(b));
25      q.push(k);
26      b[k]=1;
27      for (;!q.empty();q.pop()){
28          int x=q.front();
29          for (node *tmp=son[x];tmp;tmp=tmp->next)
30              if (!b[tmp->link]){
31                 int u=tmp->link;
32                 dis[u]=dis[x]+tmp->dt;
33                 q.push(u);
34                 b[u]=1;
35                 if (dis[u]>Max){
36                    Max=dis[u];
37                    k=u;
38                    }
39                 }
40          }
41      return k;
42 }
43 int main()
44 {
45 #ifndef ONLINE_JUDGE
46     freopen("Computer.in","r",stdin);freopen("Computer.out","w",stdout);
47 #endif
48     while (scanf("%d",&n)!=EOF){
49           memset(son,0,sizeof(son));
50           EC=0;
51           for (int i=1;i<n;++i){
52               int x,y;
53               scanf("%d%d",&x,&y);
54               addedge(x,i+1,y);
55               addedge(i+1,x,y);
56               }   
57           int s=bfs(1); 
58           s=bfs(s);
59           for (int i=1;i<=n;++i) temp[i]=dis[i];
60           bfs(s);
61           for (int i=1;i<=n;++i) printf("%d\n",max(temp[i],dis[i]));
62           }
63 #ifndef ONLINE_JUDGE
64     fclose(stdin);fclose(stdout);
65 #endif
66 }