hiho 1050 树中的最长路 (树的直径)

最近在复习比较简单的知识，顺便当整理代码吧。

树的直径是一个经典问题，即求树上最远两点的距离。

思路一：

任取一个点，求这个点的最远点的最远点，两遍bfs即可。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <functional>
14 #include <cctype>
15 #include <time.h>
16 
17 using namespace std;
18 
19 const int INF = 1<<30;
20 
21 struct Graph {
22     static const int MAXN = (int) 1e5+55;
23     static const int MAXM = MAXN*2;
24 
25     int head[MAXN];
26     int next[MAXM], to[MAXM], use;
27 
28     inline void init() {
29         memset(head, -1, sizeof(head));
30         use = 0;
31     }
32 
33     inline void addEdge(int u, int v) {
34         next[use] = head[u];
35         to[use] = v;
36         head[u] = use++;
37     }
38 };
39 
40 const int MAXN = (int) 1e5+55;
41 
42 Graph G;
43 int Que[MAXN];
44 int d[MAXN];
45 int n;
46 
47 void bfs(int st) {
48     memset(d, -1, sizeof(d));
49     int l = 0, r = 0;
50     d[st] = 0;
51     Que[r++] = st;
52     while (l<r) {
53         int u = Que[l++];
54         for (int p = G.head[u]; p != -1; p = G.next[p]) {
55             int v = G.to[p];
56             if (d[v]!=-1) continue;
57             d[v] = d[u] + 1;
58             Que[r++] = v;
59         }
60     }
61 }
62 
63 void solve() {
64     bfs(1);
65     bfs(Que[n-1]);
66     printf("%d
", d[Que[n-1]]);
67 }
68 
69 int main() {
70     #ifdef Phantom01
71         freopen("1050.txt", "r", stdin);
72     #endif //Phantom01
73 
74     while (scanf("%d", &n)!=EOF) {
75         G.init();
76         int u, v;
77         for (int i = 1; i < n; i++) {
78             scanf("%d%d", &u, &v);
79             G.addEdge(u, v);
80             G.addEdge(v, u);
81         }
82         solve();
83     }
84 
85     return 0;
86 }

View Code

另一种思路是树形dp，一棵树中的最长路要么在子树中，要么经过根。枚举每棵子树的最大深度和次大深度即可。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <functional>
14 #include <cctype>
15 #include <time.h>
16 
17 using namespace std;
18 
19 const int INF = 1<<30;
20 
21 struct Graph {
22     static const int MAXN = (int) 1e5+55;
23     static const int MAXM = MAXN*2;
24 
25     int head[MAXN];
26     int next[MAXM], to[MAXM], use;
27 
28     inline void init() {
29         memset(head, -1, sizeof(head));
30         use = 0;
31     }
32 
33     inline void addEdge(int u, int v) {
34         next[use] = head[u];
35         to[use] = v;
36         head[u] = use++;
37     }
38 };
39 
40 Graph G;
41 
42 const int MAXN = (int) 1e5+55;
43 
44 int dp[MAXN];
45 int ans;
46 
47 int dfs(int u, int pre, int cnt) {
48     int fi = 0, se = 0;
49     int t;
50 
51     for (int p = G.head[u]; p != -1; p = G.next[p]) {
52         int v = G.to[p];
53         if (v==pre) continue;
54         t = dfs(v, u, cnt+1);
55         if (t>fi) { se = fi; fi = t; }
56         else if (t>se) se = t;
57     }
58     ans = max(ans, max(fi+cnt, fi+se));
59     return fi+1;
60 }
61 
62 int main() {
63     #ifdef Phantom01
64         freopen("1050.txt", "r", stdin);
65     #endif //Phantom01
66 
67     int n, u, v;
68     while (scanf("%d", &n)!=EOF) {
69         G.init();
70         for (int i = 1; i < n; i++) {
71             scanf("%d%d", &u, &v);
72             G.addEdge(u, v);
73             G.addEdge(v, u);
74         }
75         ans = 0;
76         dfs(1, 1, 0);
77         printf("%d
", ans);
78     }
79 
80     return 0;
81 }

View Code

顺便说一下，hiho上这个题的数据比较弱，开始我几个错误的代码都A了。