这貌似是13年的noip最后一道吧？、、、
蒟蒻只会这种题呢、、、
Kruskal求出MST，然后倍增就好了
1 /************************************************************** 2 Problem: 3732 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:268 ms 7 Memory:4412 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 const int N = 16005; 15 const int M = 30005; 16 17 struct Edge { 18 int x, y, v; 19 20 inline bool operator < (const Edge &x) const { 21 return v < x.v; 22 } 23 } E[M]; 24 25 struct edge { 26 int next, to, v; 27 edge() {} 28 edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 29 } e[M]; 30 31 struct tree_node { 32 int fa[16], mx[16], dep; 33 } tr[N]; 34 35 int n, m; 36 int fa[N]; 37 int tot, first[N]; 38 39 inline int read() { 40 int x = 0; 41 char ch = getchar(); 42 while (ch < '0' || '9' < ch) 43 ch = getchar(); 44 while ('0' <= ch && ch <= '9') { 45 x = x * 10 + ch - '0'; 46 ch = getchar(); 47 } 48 return x; 49 } 50 51 inline void Add_Edges(int x, int y, int v) { 52 e[++tot] = edge(first[x], y, v), first[x] = tot; 53 e[++tot] = edge(first[y], x, v), first[y] = tot; 54 } 55 56 int find_fa(int x) { 57 return x == fa[x] ? x : fa[x] = find_fa(fa[x]); 58 } 59 60 void Kruskal() { 61 int i, cnt, fa1, fa2; 62 sort(E + 1, E + m + 1); 63 for (i = 1; i <= n; ++i) 64 fa[i] = i; 65 for (i = 1, cnt = 0; i <= m; ++i) { 66 fa1 = find_fa(E[i].x), fa2 = find_fa(E[i].y); 67 if (fa1 != fa2) { 68 fa[fa1] = fa2, ++cnt; 69 Add_Edges(E[i].x, E[i].y, E[i].v); 70 if (cnt == n - 1) break; 71 } 72 } 73 } 74 75 void dfs(int p) { 76 int x, y; 77 for (x = 1; x < 16; ++x) { 78 tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 79 tr[p].mx[x] = max(tr[p].mx[x - 1], tr[tr[p].fa[x - 1]].mx[x - 1]); 80 } 81 for (x = first[p]; x; x = e[x].next) 82 if ((y = e[x].to) != tr[p].fa[0]) { 83 tr[y].dep = tr[p].dep + 1; 84 tr[y].fa[0] = p, tr[y].mx[0] = e[x].v; 85 dfs(y); 86 } 87 } 88 89 int query(int x, int y) { 90 int res = 0, i; 91 if (tr[x].dep < tr[y].dep) swap(x, y); 92 for (i = 15; ~i; --i) 93 if (tr[tr[x].fa[i]].dep >= tr[y].dep) { 94 res = max(res, tr[x].mx[i]); 95 x = tr[x].fa[i]; 96 } 97 for (i = 15; ~i; --i) 98 if (tr[x].fa[i] != tr[y].fa[i]) { 99 res = max(res, max(tr[x].mx[i], tr[y].mx[i])); 100 x = tr[x].fa[i], y = tr[y].fa[i]; 101 } 102 if (x != y) 103 res = max(res, max(tr[x].mx[0], tr[y].mx[0])); 104 return res; 105 } 106 107 int main() { 108 n = read(), m = read(); 109 int Q = read(), i, x, y; 110 for (i = 1; i <= m; ++i) 111 E[i].x = read(), E[i].y = read(), E[i].v = read(); 112 Kruskal(); 113 tr[1].dep = 1; 114 dfs(1); 115 while (Q--) { 116 x = read(), y = read(); 117 printf("%d\n", query(x, y)); 118 } 119 return 0; 120 }
