先考虑如何求解区间 LCA
假设要我们求 \(8 \sim 11\) 的 LCA。
那么显然它们的 LCA 等效于 8 和 11 的 LCA。
发现 8 和 11 刚好是 “最左” 和 “最右” 的两个顶点，感性理解一下，就可以得出一个结论：
区间 LCA 和 dfs 序 最小的 和 最大的 的LCA 是等效的。（这个结论应该还是蛮经典的）
那么问题就转化成求区间最值，线段树基操。
回到这题，由于上述结论，删去的点显然要么是 dfs 序 最大的， 要么是 dfs 序 最小的，两种情况都做一下即可。
#include<bits/stdc++.h>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 1e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, q, tot, lg, cnt;
int Head[N], to[N << 1], Next[N << 1];
int f[N][20], dfn[N], id[N], d[N];
int minn[N << 2], maxn[N << 2];
void add(int u, int v){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs(int x, int fa){
d[x] = d[fa] + 1, dfn[x] = ++cnt, id[cnt] = x, f[x][0] = fa;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa) continue;
dfs(y, x);
}
}
void pushup(int u){
minn[u] = min(minn[ls], minn[rs]);
maxn[u] = max(maxn[ls], maxn[rs]);
}
void build(int u, int l, int r){
if(l == r) return minn[u] = maxn[u] = dfn[l], void();
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
int querymx(int u, int l, int r, int L, int R){
if(l > R || r < L) return 0;
if(L <= l && r <= R) return maxn[u];
int mid = (l + r) >> 1, ans = 0;
if(L <= mid) ans = max(ans, querymx(ls, l, mid, L, R));
if(R > mid) ans = max(ans, querymx(rs, mid + 1, r, L, R));
return ans;
}
int querymn(int u, int l, int r, int L, int R){
if(l > R || r < L) return 1e9;
if(L <= l && r <= R) return minn[u];
int mid = (l + r) >> 1, ans = 1e9;
if(L <= mid) ans = min(ans, querymn(ls, l, mid, L, R));
if(R > mid) ans = min(ans, querymn(rs, mid + 1, r, L, R));
return ans;
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = lg; ~i; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
for(int i = lg; ~i; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int main(){
n = read(), q = read(), lg = log2(n);
for(int i = 2; i <= n; ++i){
int v = read();
add(i, v), add(v, i);
}
dfs(1, 0);
build(1, 1, n);
for(int i = 1; i <= lg; ++i)
for(int j = 1; j <= n; ++j)
f[j][i] = f[f[j][i - 1]][i - 1];
while(q--){
int l = read(), r = read();
int L = querymn(1, 1, n, l, r), R = querymx(1, 1, n, l, r);
L = id[L], R = id[R];
int LL = min(querymn(1, 1, n, l, L - 1), querymn(1, 1, n, L + 1, r));
int RR = max(querymx(1, 1, n, l, R - 1), querymx(1, 1, n, R + 1, r));
LL = id[LL], RR = id[RR];
int t1 = lca(L, RR), t2 = lca(LL, R);
if(d[t1] > d[t2]) printf("%d %d\n", R, d[t1] - 1);
else printf("%d %d\n", L, d[t2] - 1);
}
return 0;
}