题意
三倍经验哇咔咔
Sol
首先可以证明,两点之间边权最大值最小的路径一定是在最小生成树上
考虑到这题是边权的最大值,直接把重构树建出来
然后查LCA处的权值即可
输入文件过大,需要用RMQ算法求LCA
// luogu-judger-enable-o2#includeconst int MAXN = 1e6 + 10;using namespace std;inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}int N, Q, S, tot, dfn[MAXN], rev[MAXN], dep[MAXN], id[MAXN][21], lg2[MAXN], rd[MAXN];vector v[MAXN];void dfs(int x, int fa) { dfn[x] = ++tot; dep[x] = dep[fa] + 1; id[tot][0] = x; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa) continue; dfs(to, x); id[++tot][0] = x; }}void RMQ() { for(int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1; for(int j = 1; j <= 20; j++) { for(int i = 1; (i + (1 << j) - 1) <= tot; i++) { int r = i + (1 << (j - 1)); id[i][j] = dep[id[i][j - 1]] < dep[id[r][j - 1]] ? id[i][j - 1] : id[r][j - 1]; } }}int Query(int l, int r) { if(l > r) swap(l, r); int k = lg2[r - l + 1]; return dep[id[l][k]] < dep[id[r - (1 << k) + 1][k]] ? id[l][k] : id[r - (1 << k) + 1][k];}int main() { freopen("a.in", "r", stdin); N = read(); Q = read(); S = read(); for(int i = 1; i <= N - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(S, 0); RMQ(); while(Q--) { int x = read(), y = read(); printf("%d\n", Query(dfn[x], dfn[y])); } return 0;}