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
2 #include
3 #include
4 #include
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
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
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 -