原题链接

我的做法是树剖预处理出dfs序等然后找LCA

// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
// #include
#define maxn 600005
using namespace std;
int a[maxn], dfn[maxn], n;
//--------------------------以下是线段树部分--------------------------
int ma[maxn][30], mi[maxn][30], log_2[maxn];
void init() {
	for (int i = 1; i <= n; i++) ma[i][0] = mi[i][0] = dfn[i];
    for(int i = 2; i <= n; i++) log_2[i] = log_2[i >> 1] + 1;
	for (int j = 1; (1 << j) <= n; j++) //会有更快的运行速度,此处意思是2^j <= n
		for (int i = 1; i <= n - (1 << j) + 1; i++) { //如果要闭区间的话需要加上一，这一点在求前缀和里也有体现
			ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]);
			mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
		}
}

int q_ma(int A, int B) {
	int x = log_2[B - A + 1];
	return max(ma[A][x], ma[B - (1 << x) + 1][x]);
}

int q_mi(int A, int B) {
	int x = log_2[B - A + 1];
	return min(mi[A][x], mi[B - (1 << x) + 1][x]); //还是，区间，尝试找出两个在A与B之间的并且重叠的区间。
}

//--------------------------以下是树剖部分-----------------------------
struct EDGE{
    int nxt, to;
}e[maxn << 1];
int head[maxn << 1], cnt;
inline void add(int a,int b){e[++cnt].nxt = head[a], e[cnt].to = b, head[a] = cnt;}

int dep[maxn], fa[maxn], son[maxn], siz[maxn];
inline int dfs1(int u,int f,int depth){
    dep[u] = depth, fa[u] = f, siz[u] = 1;
    int maxson = -1;
    for(int i = head[u]; i; i = e[i].nxt){
        int to = e[i].to;
        if(to != f){
            siz[u] += dfs1(to, u, depth + 1);
            if(siz[to] > maxson) maxson = siz[to], son[u] = to;
        }
    }
    return siz[u];
}

int top[maxn], d[maxn], mapp[maxn], tot;
inline void dfs2(int u,int fa){
    dfn[u] = ++tot, mapp[tot] = u;
    top[u] = fa;
    if(!son[u]) return;
    dfs2(son[u], fa);
    for(int i = head[u]; i; i = e[i].nxt) if(!dfn[e[i].to]) dfs2(e[i].to, e[i].to);
}
//--------------------------以上是树剖部分-----------------------------
inline int LCA(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] <= dep[y]) return x;
    else return y;  
}

int l, r, q;

int main(){
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d", &n);
    for(int i = 1, u, v; i <= n - 1; i++) scanf("%d %d", &u, &v), add(u, v), add(v, u);
    dfs1(1, 0, 1), dfs2(1, 1);
    init();
    scanf("%d", &q);
    while(q--){
        scanf("%d %d", &l, &r);
        printf("%d\n",LCA(mapp[q_mi(l, r)], mapp[q_ma(l, r)]));
    }
    return 0;
}