P2245 样例没过求助

不会树剖所以只写了倍增

#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 3e5 + 5;
const int maxp = 20 + 5;
const int INF = 2147483647;

int n, m, A, B, Q;
//int Edgetot, Edgefrom[maxm << 1], Edgeto[maxm << 1], Edgeval[maxm << 1];
int Edgetot;

struct Node {
	int fr, to, val;
	bool operator < (const Node & x) {
		return x.val > val;
	}
}Edge[maxm << 1]; 

void Edgeadd(int u, int v, int c) {
	Edgetot++;
	Edge[Edgetot].fr = u;
	Edge[Edgetot].to = v;
	Edge[Edgetot].val = c;
}

int tot, hd[maxn], to[maxm << 1], nxt[maxm << 1], val[maxn << 1];

void add(int u, int v, int c) {
	tot++;
	nxt[tot] = hd[u];
	hd[u] = tot;
	to[tot] = v;
	val[tot] = c;
}

int fa[maxn << 1], k;
int Find(int x) {
	return (x == fa[x]) ? x : fa[x] = Find(fa[x]);
}

int dep[maxn], fat[maxn][maxp], Pathval[maxn][maxp];
void dfs(int x, int father) {
	dep[x] = dep[father] + 1;
	fat[x][0] = father;
	for (int i = 1;i < maxp;i++) fat[x][i] = fat[fat[x][i - 1]][i - 1], Pathval[x][i] = Pathval[fat[x][i - 1]][i - 1];
	
	for (int i = hd[x];i;i = nxt[i]) {
		int v = to[i];
		if (v == father) continue;
		Pathval[v][0] = val[i];
		dfs(v, x);
	}
}

int LCA(int x, int y) {
	int MaxPathval = -INF;
	
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = maxp - 1;i >= 0;i--) if (dep[x] - (1 << i) >= dep[y]) {
		x = fat[x][i];
		MaxPathval = max(MaxPathval, Pathval[x][i]);
	}
	
	if (x == y) return MaxPathval;
	
	for (int i = maxp - 1;i >= 0;i--) if (fat[x][i] != fat[y][i]) {
		x = fat[x][i];
		y = fat[y][i];
		MaxPathval = max({MaxPathval, Pathval[x][i], Pathval[y][i]});
	}
	
	MaxPathval = max({MaxPathval, Pathval[x][0], Pathval[y][0]});
	return MaxPathval;
}

int main() {
	n = read(), m = read();
	for (int i = 1;i <= m;i++) {
		int u = read(), v = read(), c = read();
		Edgeadd(u, v, c), Edgeadd(v, u, c);
	}
	
	sort(Edge + 1, Edge + 1 + m * 2);
//	for (int i = 1;i <= m * 2;i++) cout << Edge[i].val << ' ';
//	putchar(10); 
	
	for (int i = 1;i <= n * 2;i++) fa[i] = i;k = n;
	for (int i = 1;i <= m;i++) {
		int u = Edge[i].fr, v = Edge[i].to, Val = Edge[i].val;
		int Fau = Find(u), Fav = Find(v);
		if (Fau == Fav) continue;
//		k++, fa[u] = k, fa[v] = k;
		k++, fa[Fau] = k, fa[Fav] = k;
//		add(u, k), add(k, u), add(v, k), add(k, v);
		add(Fau, k, Val), add(k, Fau, Val), add(Fav, k, Val), add(k, Fav, Val);
	}
	
	dfs(1, 0);
	
	Q = read();
	while (Q--) {
		int A = read(), B = read();
		if (Find(A) != Find(B)) puts("impossible");
		else write(LCA(A, B)), putchar(10);
	}
	return 0;
}