1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
#define maxm 50010
#define Maxn 20010
#define cE const Edge
using namespace std;
int n, m, q;
struct Edge {
int fr, to, w;
friend bool operator < (cE &u, cE &v) { return u.w > v.w; }
} e[maxm];
int fa[Maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
#define lc T[u].ch[0]
#define rc T[u].ch[1]
struct Tree {
int v, ch[2];
} T[Maxn]; int top, rt;
int dep[Maxn], f[Maxn][21];
void dfs(int u, int fa, int d) {
if (!u) return ;
dep[u] = d; f[u][0] = fa;
dfs(lc, u, d + 1); dfs(rc, u, d + 1);
}
void init_lca(int n) {
for (int j = 1; j <= 20; ++j)
for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}
int get_lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; ~i; --i)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (x == y) return x;
for (int i = 20; ~i; --i)
if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].fr, &e[i].to, &e[i].w);
sort(e + 1, e + m + 1); init_fa(2 * n); top = n;
for (int i = 1; i <= m; ++i) {
int u = e[i].fr, v = e[i].to, w = e[i].w, fu, fv;
if ((fu = find(u)) == (fv = find(v))) continue;
fa[fu] = fa[fv] = ++top; T[top].ch[0] = fu; T[top].ch[1] = fv;
T[top].v = w;
}
for (int i = top; i; --i)
if (!dep[i]) dfs(i, 0, 1);
cin >> q; init_lca(top); T[0].v = -1;
for (int i = 1; i <= q; ++i) {
int x, y, g; scanf("%d%d", &x, &y);
g = get_lca(x, y); printf("%d\n", T[g].v);
}
return 0;
}
|