HDU 3848 CC On The Tree（树形dp）

http://acm.hdu.edu.cn/showproblem.php?pid=3848

题意：

求一棵树上两个叶子结点之间的最短距离。

思路：

两个叶子节点之间一定会经过非叶子节点，除非只有两个节点。

所以我们只需要维护离每个非叶子节点最远的叶子节点距离和次远距离，两者相加即是两个叶子节点之间的距离。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn = 10000+5;
17 
18 int n;
19 int d[maxn][2];
20 vector<pll> G[maxn];
21 
22 void dfs(int u, int fa)
23 {
24     d[u][0]=d[u][1]=INF;
25     if(G[u].size()==1)
26     {
27         d[u][0]=0;
28         return ;
29     }
30     for(int i=0;i<G[u].size();i++)
31     {
32         int v=G[u][i].first;
33         int w=G[u][i].second;
34         if(v==fa)  continue;
35         dfs(v,u);
36         if(d[u][0]>d[v][0]+w)
37         {
38             d[u][1]=d[u][0];
39             d[u][0]=d[v][0]+w;
40         }
41         else if(d[u][1]>d[v][0]+w)
42             d[u][1]=d[v][0]+w;
43     }
44 }
45 
46 int main()
47 {
48     //freopen("in.txt","r",stdin);
49     while(~scanf("%d",&n) && n)
50     {
51         for(int i=1;i<=n;i++)  G[i].clear();
52         for(int i=1;i<n;i++)
53         {
54             int u,v,w;
55             scanf("%d%d%d",&u,&v,&w);
56             G[u].push_back(make_pair(v,w));
57             G[v].push_back(make_pair(u,w));
58         }
59         if(n==2)
60         {
61             printf("%d
",G[1][0].second);
62             continue;
63         }
64         int i;
65         for(i=1;i<=n;i++)  if(G[i].size()>1)  break;
66         dfs(i,-1);
67         int ans=INF;
68         for(int i=1;i<=n;i++)
69             ans=min(ans,d[i][0]+d[i][1]);
70         printf("%d
",ans);
71 
72     }
73     return 0;
74 }