84pts wa on #1#2求条

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXM = 3e5 + 5;
const int LOG = 20;
int n, m;
struct Edge {
	int v, w;
};
struct edge {
	int u, v, w;
	bool operator < (const edge &other) const {
		return w < other.w;
	}
}e[MAXM];
vector<Edge> g[MAXN];
int fa_set[MAXN];
struct LCA {
	int fa[MAXN][LOG], mx[MAXN][LOG], dep[MAXN];
	int LOG2(int x) {
		return 31 - __builtin_clz(x);
	}
	void dfs(int u, int pa, int w) {
		fa[u][0] = pa;
		mx[u][0] = w;
		dep[u] = dep[pa] + 1;
		for (int i = 1; i < LOG; i++) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
			mx[u][i] = max(mx[u][i - 1], mx[fa[u][i - 1]][i - 1]);
		}
		for (Edge ed : g[u]) {
			int v = ed.v, ww= ed.w;
			if (v != pa) {
				dfs(v, u, ww);
			}
		}
	}
	int query(int u, int v) {
		int ans = 0;
		if (dep[u] < dep[v]) swap(u, v);
		for (int i = LOG - 1; i >= 0; i--) {
			if (dep[fa[u][i]] >= dep[v]) {
				ans = max(ans, mx[u][i]);
				u = fa[u][i];
			}
		}
		if (u == v) return ans;
		for (int i = LOG - 1; i >= 0; i--) {
			if (fa[u][i] != fa[v][i]) {
				ans = max({mx[u][i], mx[v][i], ans});
				u = fa[u][i], v = fa[v][i];
			}
		}
		return max({ans, mx[u][0], mx[v][0]});
	}
}l;
int find_set(int x) {
	return x == fa_set[x] ? x : fa_set[x] = find_set(fa_set[x]);
}
void addEdge(int u, int v, int w) {
	g[u].push_back({v, w});
	g[v].push_back({u, w});
}
void kruskal() {
	sort(e + 1, e + m + 1);
	for (int i = 1; i <= n; i++) {
		fa_set[i] = i;
	}
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		if (cnt == n - 1) break;
		int u = e[i].u, v = e[i].v, w = e[i].w;
		if (find_set(u) != find_set(v)) {
			cnt++;
			addEdge(u, v, w);
			fa_set[find_set(u)] = find_set(v);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	kruskal();
	l.dfs(1, 0, 0);
	int q;
	cin >> q;
	while(q--) {
		int u, v;
		cin >> u >> v;
		if (find_set(u) != find_set(v)) {
			cout << "impossible" << endl;
			continue;
		}
		cout << l.query(u, v) << endl;
	}
	return 0;
}