描述
有一棵樹，樹上有只毛毛蟲。它在這棵樹上生活了很久，對它的構造了如指掌。所以它在樹上從來都是走最短路，不會繞路。它還還特別喜歡三角形，所以當它在樹上爬來爬去的時候總會在想，如果把剛才爬過的那幾根樹枝/樹干鋸下來，能不能從中選三根出來拼成一個三角形呢？
輸入
輸入數據的第一行包含一個整數 T，表示數據組數。
接下來有 T 組數據，每組數據中：
第一行包含一個整數 N，表示樹上節點的個數（從 1 到 N 標號）。
接下來的 N-1 行包含三個整數 a, b, len，表示有一根長度為 len 的樹枝/樹干在節點 a 和節點 b 之間。
接下來一行包含一個整數 M，表示詢問數。
接下來M行每行兩個整數 S, T，表示毛毛蟲從 S 爬行到了 T，詢問這段路程中的樹枝/樹干是否能拼成三角形。
輸出
對於每組數據，先輸出一行"Case #X:",其中X為數據組數編號，從 1 開始。
接下來對於每個詢問輸出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
數據范圍
1 ≤ T ≤ 5
小數據：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000
大數據：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
樣例輸入
251 2 51 3 202 4 304 5 1523 43 551 4 322 3 1003 5 454 5 6021 41 3樣例輸出
Case #1:NoYesCase #2:NoYes解題思路
這道題如果直接按照題意去寫，那麼可以利用廣度優先搜索得到最短路徑（因為這是一顆樹，而不是圖，所以不必使用最短路算法），然後判斷路徑上的邊是否能組成一個三角形（先對路徑排序，然後用兩邊之和大於第三邊進行判斷）。不過搜索的時間復雜度是 O(N)，判斷三角形的時間復雜度為 O(llgl)（其中 l 是最短路徑的長度），小數據沒問題，但大數據肯定會掛。
判斷三角形是否存在，我並沒有更好的辦法，那麼只能在求最短路徑上下手了，以下面的樹作為例子（題目沒說是幾叉樹，不過沒有關系）：
圖 1 一顆樹的示例
求一棵樹上兩個節點的最短路徑，其實就是求兩個節點的最近公共祖先（Least Common Ancestors，LCA）。最近公共祖先指的是在一顆有根樹中，找到兩個節點 u 和 v 最近的公共祖先。這個概念很容易理解，例如上面節點 5 和 10 的 LCA 就是 1，3 和 11 的 LCA 是 3，7 和 9 的 LCA 是 3。
顯然，兩個節點與它們的最近公共祖先之間的路徑（可以不斷向上查找父節點得到）加起來，就是兩個節點間的最短路徑。上面節點 5 和 10 的最短路徑就為 5、2、1、3、8、10；節點 3 和 11 的最短路徑就為 3、8、9、11。
求 LCA 有兩種算法，一種是離線的 Tarjan 算法，計算出所有 M 個詢問所需的時間復雜度是 O(N+M)；另一種是基於區間最值查詢（Range Minimum/Maximum Query，RMQ）的在線算法，預處理時間是 O(NlgN)，每次詢問的時間復雜度為 O(1)，總得時間復雜度就是 O(NlgN+M)。兩個算法使用那個都可以，不過感覺還是用 Tarjan 更好點，占用內存更少，速度也更快。關於這兩個算法的詳細解釋，可以參見算法之LCA與RMQ問題，這裡就不詳細說明了。
在線算法的代碼
View Code
1 #include <stdio.h>
2 #include <cmath>
3 #include <algorithm>
4 #include <list>
5 #include <string.h>
6 using namespace std;
7 // 樹的節點
8 struct Node {
9 int next, len;
10 Node (int n, int l):next(n), len(l) {}
11 };
12 int pow2[20];
13 list<Node> nodes[100010];
14 bool visit[100010];
15 int ns[200010];
16 int nIdx;
17 int length[100010];
18 int parent[100010];
19 int depth[200010];
20 int first[100010];
21 int mmin[20][200010];
22 int edges[100010];
23 // DFS 對樹進行預處理
24 void dfs(int u, int dep)
25 {
26 ns[++nIdx] = u; depth[nIdx] = dep;
27 visit[u] = true;
28 if (first[u] == -1) first[u] = nIdx;
29 list<Node>::iterator it = nodes[u].begin(), end = nodes[u].end();
30 for (;it != end; it++)
31 {
32 int v = it->next;
33 if(!visit[v])
34 {
35 length[v] = it->len;
36 parent[v] = u;
37 dfs(v, dep + 1);
38 ns[++nIdx] = u;
39 depth[nIdx] = dep;
40 }
41 }
42 }
43 // 初始化 RMQ
44 void init_rmq()
45 {
46 nIdx = 0;
47 memset(visit, 0, sizeof(visit));
48 memset(first, -1, sizeof(first));
49 depth[0] = 0;
50 length[1] = parent[1] = 0;
51 dfs(1, 1);
52 memset(mmin, 0, sizeof(mmin));
53 for(int i = 1; i <= nIdx; i++) {
54 mmin[0][i] = i;
55 }
56 int t1 = (int)(log((double)nIdx) / log(2.0));
57 for(int i = 1; i <= t1; i++) {
58 for(int j = 1; j + pow2[i] - 1 <= nIdx; j++) {
59 int a = mmin[i-1][j], b = mmin[i-1][j+pow2[i-1]];
60 if(depth[a] <= depth[b]) {
61 mmin[i][j] = a;
62 } else {
63 mmin[i][j] = b;
64 }
65 }
66 }
67 }
68 // RMQ 詢問
69 int rmq(int u, int v)
70 {
71 int i = first[u], j = first[v];
72 if(i > j) swap(i, j);
73 int t1 = (int)(log((double)j - i + 1) / log(2.0));
74 int a = mmin[t1][i], b = mmin[t1][j - pow2[t1] + 1];
75 if(depth[a] <= depth[b]) {
76 return ns[a];
77 } else {
78 return ns[b];
79 }
80 }
81
82 int main() {
83 for(int i = 0; i < 20; i++) {
84 pow2[i] = 1 << i;
85 }
86 int T, n, m, a, b, len;
87 scanf("%d ", &T);
88 for (int caseIdx = 1;caseIdx <= T;caseIdx++) {
89 scanf("%d", &n);
90 for (int i = 0;i <= n;i++) {
91 nodes[i].clear();
92 }
93 for (int i = 1;i < n;i++) {
94 scanf("%d%d%d", &a, &b, &len);
95 nodes[a].push_back(Node(b, len));
96 nodes[b].push_back(Node(a, len));
97 }
98 init_rmq();
99 scanf("%d", &m);
100 printf("Case #%d:\n", caseIdx);
101 for (int i = 0;i < m;i++) {
102 scanf("%d%d", &a, &b);
103 // 利用 RMQ 得到 LCA
104 int root = rmq(a, b);
105 bool success = false;
106 int l = 0;
107 while (a != root) {
108 edges[l++] = length[a];
109 a = parent[a];
110 }
111 while (b != root) {
112 edges[l++] = length[b];
113 b = parent[b];
114 }
115 if (l >= 3) {
116 sort(edges, edges + l);
117 for (int j = 2;j < l;j++) {
118 if (edges[j - 2] + edges[j - 1] > edges[j]) {
119 success = true;
120 break;
121 }
122 }
123 }
124 if (success) {
125 puts("Yes");
126 } else {
127 puts("No");
128 }
129 }
130 }
131 return 0;
132 }離線算法的代碼
View Code
1 #include <stdio.h>
2 #include <string.h>
3 #include <list>
4 #include <algorithm>
5 using namespace std;
6 // 樹和查詢的節點
7 struct Node {
8 int next, len;
9 Node (int n, int l):next(n), len(l) {}
10 };
11 list<Node> nodes[100010];
12 list<Node> querys[100010];
13 bool visit[100010];
14 int ancestor[100010];
15 int parent[100010];
16 int length[100010];
17 int edges[100010];
18 // 查詢的結果
19 bool result[100010];
20 // 並查集
21 int uset[100010];
22 int find(int x) {
23 int p = x, t;
24 while (uset[p] >= 0) p = uset[p];
25 while (x != p) { t = uset[x]; uset[x] = p; x = t; }
26 return x;
27 }
28 void un_ion(int a, int b) {
29 if ((a = find(a)) == (b = find(b))) return;
30 if (uset[a] < uset[b]) { uset[a] += uset[b]; uset[b] = a; }
31 else { uset[b] += uset[a]; uset[a] = b; }
32 }
33 void init_uset() {
34 memset(uset, -1, sizeof(uset));
35 }
36
37 void tarjan(int u) {
38 visit[u] = true;
39 ancestor[find(u)] = u;
40 list<Node>::iterator it = nodes[u].begin(), end = nodes[u].end();
41 for (;it != end; it++)
42 {
43 int v = it->next;
44 if(!visit[v])
45 {
46 length[v] = it->len;
47 parent[v] = u;
48 tarjan(v);
49 un_ion(u, v);
50 ancestor[find(u)] = u;
51 }
52 }
53 it = querys[u].begin(); end = querys[u].end();
54 for (;it != end; it++)
55 {
56 int v = it->next;
57 if(visit[v])
58 {
59 // 處理從 u 起始的查詢
60 int root = ancestor[find(v)];
61 int l = 0;
62 int a = u;
63 while (a != root) {
64 edges[l++] = length[a];
65 a = parent[a];
66 }
67 while (v != root) {
68 edges[l++] = length[v];
69 v = parent[v];
70 }
71 sort(edges, edges + l);
72 for (int j = 2;j < l;j++) {
73 if (edges[j - 2] + edges[j - 1] > edges[j]) {
74 result[it->len] = true;
75 break;
76 }
77 }
78 }
79 }
80 }
81
82 int main() {
83 int T, n, m, a, b, len;
84 scanf("%d ", &T);
85 for (int caseIdx = 1;caseIdx <= T;caseIdx++) {
86 scanf("%d", &n);
87 for (int i = 0;i <= n;i++) {
88 nodes[i].clear();
89 querys[i].clear();
90 }
91 for (int i = 1;i < n;i++) {
92 scanf("%d%d%d", &a, &b, &len);
93 nodes[a].push_back(Node(b, len));
94 nodes[b].push_back(Node(a, len));
95 }
96 scanf("%d", &m);
97 for (int i = 0;i < m;i++) {
98 scanf("%d%d", &a, &b);
99 // 查詢要添加兩遍，以防止出現遺漏
100 querys[a].push_back(Node(b, i));
101 querys[b].push_back(Node(a, i));
102 }
103 printf("Case #%d:\n", caseIdx);
104 init_uset();
105 memset(visit, 0, sizeof(visit));
106 memset(result, 0, sizeof(result));
107 length[1] = parent[1] = 0;
108 tarjan(1);
109 for (int i = 0;i < m;i++) {
110 if (result[i]) {
111 puts("Yes");
112 } else {
113 puts("No");
114 }
115 }
116 }
117 return 0;
118 }這兩個算法應該是沒問題的，但大數據的時候都 TLE 了，看來 list 真不能隨便用，動態開辟內存還是太慢了。離線算法的內存使用大概只有在線算法的 70%。
後來我翻代碼的時候（所有人的代碼都可以看到，這點挺給力），看到有人沒用上面的 LCA 算法，而是在用 DFS 建好樹後，使要判斷的兩個節點 u 和 v 分別沿著父節點鏈向上遍歷，同時保持 u 和 v 的深度是相同的，這樣同樣能得到最短路徑和 LCA，只不過時間復雜度要高一些。但在這道題中也沒有關系，因為在找三角形時還是需要把路徑遍歷一編才可以，LCA 的計算反而會帶來額外的復雜性，看來的確是自己想復雜了。
這段遍歷算法大概類似於下面這樣：
1 while (deep(u) > deep(v)){
2 // 記錄路徑 u 到 parent(u) 的路徑
3 u = parent(u);
4 }
5 while (deep(v) > deep(u)){
6 // 記錄路徑 v 到 parent(v) 的路徑
7 v = parent(v);
8 }
9 while (u != v){
10 // 記錄路徑 u 到 parent(u) 的路徑
11 u = parent(u);
12 // 記錄路徑 v 到 parent(v) 的路徑
13 v = parent(v);
14 }完整的代碼見這裡，ID 是 mochavic（排名第一），果然是大神。
