\(* \text{Defficult:} \color{Gold}{2300}\)
Description
给定一棵 \(n\) 个节点的树，有 \(q\) 个询问，每次询问给出一个区间 \(l,r\)。
要求在编号在 \([l,r]\) 范围内的点内删掉一个点后剩余点的 LCA 深度最大。
求删掉点的编号和此时 LCA 的最大深度。
Solution
首先，要做这题有一个很重要的性质：一部分节点的 LCA 一定是其中 dfs 序最大和最小的点的 LCA。
proof
设点 \(i\) 的 dfs 序为 \(id_i\)，\(id'_u=\max{id_v}\)，某个区间的 dfs 序最值所在点分别为 \(u,v\)，其 LCA 为 \(l\)。
显然有 \(id_l \le id_v \le id_u \le id'_l\)。
对于 \(\forall x \in [l,r]\)，\(id_v \le id_x \le id_u \implies id_l \le id_x \le id'_r \implies l\) 是点 \(x\) 的祖先。
所以，被删去的节点要么是 \(u\)，要么是 \(v\)。
Q.E.D
所以，我们可以枚举删去的节点是 \(u\) 和 \(v\) 的情况下的 LCA，取其中更大的值即可。
区间的 dfs 序最值，可以用数据结构维护，比如线段树，ST 表等。
假设删去了节点 \(u\)，查询就会被分成 \([l,u-1]\) 和 \([u+1,r]\) 两部分。
那就分别求出这两部分的 LCA，再取这两部分的 LCA 的 LCA 作为删去 \(u\) 时的答案，\(v\) 也同理。
注意这里要特判一下，如果 \(u,v\) 刚好就是 \(l\) 或 \(r\)，就只剩一个部分，直接返回其 LCA 即可。
求 LCA 可以用除了暴力外的所有方法，因为此题要用到 dfs 序，所以笔者使用了比较冷门的 dfs 序求 LCA。
具体细节参照代码。
时间复杂度：\(O((n+q) \log_2 n)\)
code
/*******************************
| Author: A.I.skeleton
| Problem: E. Company
| Contest: Codeforces Round #520 (Div. 2)
| URL: https://codeforces.com/contest/1062/problem/E
| When: 2022-10-25 14:25:10
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc p<<1|1
#define F(i) (i).first
#define S(i) (i).second
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define FST ios::sync_with_stdio(0);cin.tie(0);
const int N=1e5+100,INF=1e9;
int n,q,p,lg[N],cn,id[N],d[N]={-1},st[19][N];
vi g[N];int si[N],h[N],t[N],l,r;
struct se{int l,r;pi ma,mi;}s[N<<2];
void pp(int p){
s[p].ma=max(s[lc].ma,s[rc].ma);
s[p].mi=min(s[lc].mi,s[rc].mi);
}void build(int p,int l,int r){
s[p].l=l;s[p].r=r;
if(l==r) return ;
int m=(l+r)>>1;build(lc,l,m);build(rc,m+1,r);
}void change(int p,int x,int k){
if(s[p].l>x||x>s[p].r) return;
if(s[p].l==s[p].r){
S(s[p].mi)=S(s[p].ma)=s[p].l;
F(s[p].mi)=F(s[p].ma)=k;return ;
}int m=(s[p].l+s[p].r)>>1;
change(lc,x,k);change(rc,x,k);pp(p);
}pi askmi(int p,int l,int r){
if(s[p].l>r||l>s[p].r) return {INF,0};
if(l<=s[p].l&&s[p].r<=r) return s[p].mi;
return min(askmi(lc,l,r),askmi(rc,l,r));
}pi askma(int p,int l,int r){
if(s[p].l>r||l>s[p].r) return {-INF,0};
if(l<=s[p].l&&s[p].r<=r) return s[p].ma;
return max(askma(lc,l,r),askma(rc,l,r));
}int get(int x,int y){return d[x]<d[y]?x:y;}
void dfs(int u,int f){
st[0][id[u]=++cn]=f;change(1,u,id[u]);
d[u]=d[f]+1;for(int v:g[u]) if(v^f) dfs(v,u);
}int lca(int u,int v){
if(u==v) return u;if((u=id[u])>(v=id[v])) swap(u,v);
int d=lg[v-u++];return get(st[d][u],st[d][v-(1<<d)+1]);
}int sol(int l,int r,int cnt){
if(cnt==l) return lca(S(askma(1,l+1,r)),S(askmi(1,l+1,r)));
else if(cnt==r) return lca(S(askma(1,l,r-1)),S(askmi(1,l,r-1)));
else return lca(lca(S(askma(1,l,cnt-1)),S(askmi(1,l,cnt-1))),
lca(S(askma(1,cnt+1,r)),S(askmi(1,cnt+1,r))));
}int main(){
FST;cin>>n>>q;L(i,2,n) lg[i]=lg[i>>1]+1;build(1,1,n);
L(i,2,n) cin>>p,g[p].pb(i),g[i].pb(p);dfs(1,0);
L(i,1,lg[n]) L(j,1,(n+1-(1<<i)))
st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
L(i,1,q){
cin>>l>>r;
pi t1=askma(1,l,r),t2=askmi(1,l,r);
int l1=sol(l,r,S(t1)),l2=sol(l,r,S(t2));
if(d[l1]>d[l2]) cout<<S(t1)<<' '<<d[l1]<<'\n';
else cout<<S(t2)<<' '<<d[l2]<<'\n';
}
}
目前是洛谷最优解。
标签：lg,le,int,dfs,CF1062E,LCA,id From： https://www.cnblogs.com/AIskeleton/p/16825856.html