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（排名第一），果然是大神。