描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？
输入
输入数据的第一行包含一个整数 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
2 #include
3 #include
4 #include
5 #include
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
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
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()