题目传送门
LCA，三维数点，cdq 分治。
题意
给定一颗树，定义 \(\text{LCA*}(l, r)\) 为编号在 \([l, r]\) 中所有结点的最近公共祖先，即 \(l, l + 1, \dots , r\) 的公共祖先结点中深度最大的结点。
给定 \(q\) 个询问。每个询问给出三个参数 \(l, r, k\)，试求 \([l, r]\) 中任意长度大于等于 \(k\) 的连续子区间的最近公共祖先深度的最大值，即
\[\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}
\]
数据范围：
\(1 ≤ n, q ≤ 5 × 10^5 , 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r - l + 1\)
题解
首先有一个结论（跟建虚树的二次排序方法相关）：\(\text{LCA*}(l, r)\) 就是 \(\forall i \in [l,r),\text{LCA}(i,i+1)\) 中深度最小的那个 \(\text{LCA}\)。
那么就有一个显然的转化：
\[\text{dep}_ {\text{LCA*}(l', r')} = \min \limits _{i\in [l,r)} \text{dep}_{\text{lca}(i,i+1)}
\]
我们将 \(\text{dep}_{\text{lca}(i,i+1)}\) 视作序列中的元素，于是原问题就变成了求 \([l,r]\) 中的符合要求的区间元素 \(\min\) 的最大值。
由于可以离线，我们就可以考虑维护出每个元素的影响区间 \([L,R]\)，它必须是某段区间的最小值才可能被计算到，所以可以用单调栈简单处理。
现在，我们考察一个元素要成为一个询问可能的答案，要满足怎样的条件，不难想到 \([L,R] \cap [l,r]\) 的大小至少为 \(k\)（注意大小写字母 \(l,L\) 的不同定义），于是有：
\[L\le r-k+1 \\
R\ge l+k-1 \\
R-L+1\ge k \\
\]
三维数点，\(\text{cdq}\) 分治就完了。
代码
#include <bits/stdc++.h>using namespace std;
const int N=1e6+5;int n,q;
int b[N],st[N],tp;
struct node{int l,r,len,id,dep;
}a[N],c[N];
int ans[N];inline bool cmp1(const node &x,const node &y){if(x.len!=y.len) return x.len>y.len;return x.id<y.id;
}
inline bool cmp2(const node &x,const node &y){if(x.r!=y.r) return x.r>y.r;return x.id<y.id;
}vector<int> e[N];
int dep[N],top[N],fa[N],sz[N],son[N];void dfs1(int u,int f){fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;for(auto v:e[u]){if(v==f) continue;dfs1(v,u);sz[u]+=sz[v];if(sz[v]>sz[son[u]]) son[u]=v;}
}void dfs2(int u,int t){top[u]=t;if(!son[u]) return;dfs2(son[u],t);for(auto v:e[u]){if(v==fa[u]||v==son[u]) continue;dfs2(v,v);}
}inline int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);u=fa[top[u]];}return dep[u]<dep[v]?u:v;
}int f[20][N],lg2[N];void init(){lg2[0]=-1;for(int i=1;i<=n;i++) lg2[i]=lg2[i>>1]+1;for(int i=1;i<=n;i++) f[0][i]=dep[i];for(int j=1;j<=lg2[n];j++)for(int i=1;i<=n;i++)f[j][i]=max(f[j-1][i],f[j-1][i+(1<<j-1)]);
}int rmq(int l,int r){int k=lg2[r-l+1];return max(f[k][r-(1<<k)+1],f[k][l]);
}namespace BIT{int t[N];void add(int x,int y){for(;x<N;x+=x&-x) t[x]=max(t[x],y);}inline int ask(int x){int res=0;for(;x;x-=x&-x) res=max(res,t[x]);return res;}void del(int x){for(;x<N;x+=x&-x) t[x]=0;}
}void cdq(int l,int r){if(l==r) return; int mid=l+r>>1;int tot=0;for(int i=l;i<=mid;i++) if(!a[i].id) c[++tot]=a[i];for(int i=mid+1;i<=r;i++) if(a[i].id) c[++tot]=a[i];sort(c+1,c+tot+1,cmp2);for(int i=1;i<=tot;i++){if(!c[i].id) BIT::add(c[i].l,c[i].dep);else ans[c[i].id]=max(ans[c[i].id],BIT::ask(c[i].l));}for(int i=1;i<=tot;i++) if(!c[i].id) BIT::del(c[i].l); cdq(l,mid);cdq(mid+1,r);
}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;e[u].emplace_back(v);e[v].emplace_back(u);}dfs1(1,0);dfs2(1,1);for(int i=1;i<n;i++) b[i]=dep[lca(i,i+1)];int idx=0;b[0]=INT_MIN;st[tp=1]=0;for(int i=1;i<n;i++){while(b[st[tp]]>=b[i]) tp--;a[i].l=st[tp]+1;st[++tp]=i;}st[tp=1]=n;b[n]=INT_MIN;for(int i=n-1;i>=1;i--){while(b[st[tp]]>=b[i]) tp--;a[i].r=st[tp]-1;st[++tp]=i;} idx=n-1;for(int i=1;i<=idx;i++) a[i].r++,a[i].dep=b[i],a[i].len=a[i].r-a[i].l+1;init();cin>>q;for(int i=1;i<=q;i++){int l,r,k;cin>>l>>r>>k;if(k!=1){++idx;a[idx].l=r-k+1;a[idx].r=l+k-1;a[idx].len=k;a[idx].id=i;}else ans[i]=(l==r?dep[l]:rmq(l,r));}sort(a+1,a+idx+1,cmp1);cdq(1,idx);for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";return 0;
}