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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(int i = 0; i < (n); i++)
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m;
int p[maxn];
struct edge
{
int from, to, dist;
};
vector<edge>edges;
int cmp(const edge& a, const edge& b) { return a.dist < b.dist; }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
vector<edge>mst;
vector<int>G[maxn], gmst[maxn];
void add_edge(int u, int v, int w) {
edges.push_back(edge{ u,v,w });
G[u].push_back(edges.size() - 1);
edges.push_back(edge{ v,u,w });
G[v].push_back(edges.size() - 1);
}
void add_mst(int u, int v, int w) {
mst.push_back(edge{ u,v,w });
gmst[u].push_back(mst.size() - 1);
mst.push_back(edge{ v,u,w });
gmst[v].push_back(mst.size() - 1);
}
void Kruskal() {
REP(i, n + 1)p[i] = i;
sort(edges.begin(), edges.end(), cmp);
REP(i, edges.size()) {
edge& e = edges[i];
int x = find(e.from), y = find(e.to);
if (x != y) { add_mst(e.from, e.to, e.dist); p[x] = y; }
}
}
int cost[maxn], depth[maxn], f[maxn][100], maxcost[maxn][100];
void dfs(int u, int fa) {
f[u][0] = fa;
depth[u] = depth[fa] + 1;
for (int i = 1; (1 << i) <= depth[u]; ++i)
f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = 1; (1 << i) <= depth[u]; ++i)
maxcost[u][i] = max(maxcost[f[u][i - 1]][i - 1], maxcost[u][i - 1]);
REP(i, gmst[u].size()) {
edge& e = mst[gmst[u][i]];
if (e.to != fa) {
maxcost[e.to][0] = e.dist;
dfs(e.to, u);
}
}
}
int solve(int u, int v) {
int ans = 0;
if (depth[u] < depth[v])swap(u, v);
for (int i = 20; i >= 0; --i) {
if ((1 << i) <= depth[u] - depth[v]) {
ans = max(ans, maxcost[u][i]);
u = f[u][i];
}
}
if (u == v)return ans;
for (int i = 20; i >= 0; --i) {
if (f[u][i] != f[v][i]) {
ans = max(ans, max(maxcost[u][i], maxcost[v][i]));
u = f[u][i];
v = f[v][i];
}
}
ans = max(ans, max(maxcost[u][0], maxcost[v][0]));
return ans;
}
int main() {
bool fir = 1;
while (~scanf("%d%d", &n, &m)) {
if (!fir)printf("\n");
else fir = 0;
edges.clear(); mst.clear();
REP(i, n + 1)G[i].clear(), gmst[i].clear();
memset(p, 0, sizeof(p));
memset(cost, 0, sizeof(cost));
memset(depth, 0, sizeof(depth));
memset(f, 0, sizeof(f));
memset(maxcost, 0, sizeof(maxcost));
REP(i, m) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
}
Kruskal();
dfs(1, 1);
int Q;
scanf("%d", &Q);
REP(i, Q) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", solve(u, v));
}
}
return 0;
}
|
