标题是来骗你点进来帮我改 NOIP 2024 T4 的。

前几天我们开学在阴暗的教室学文化课的时候，在世界的某个教练里某个 PVP 大佬在和她的 npy 约会……现在楼主已经退役四个月了快来帮帮楼主完成儿时的梦想吧……

不会写树上启发式合并，所以就改成单调栈求每个 LCA 管的区间了；不会交集关系推到于是就用 $L\le qr-k+1,R \ge ql+k-1,R-L+1 \ge k$ 硬上三维偏序草了。做法是分治 $L$ 这一维，排序 $R$ 这一维，数据结构 $k$ 这一维。

过了样例但没过大样例……能不能给个 hack 啊……

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
const int inf=1e9+7;
int N,Q;
int head[maxn],nxt[maxn<<1],to[maxn<<1],cnt_edge;
inline void AddEdge(int u,int v){nxt[++cnt_edge]=head[u];to[cnt_edge]=v;head[u]=cnt_edge;} 
int dep[maxn],Fa[maxn],cz[maxn],Hd[maxn],Hson[maxn],dfn[maxn],dfc,ifn[maxn];
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;cz[u]=1;Fa[u]=fa;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		dfs1(v,u);cz[u]+=cz[v];
		if(cz[v]>cz[Hson[u]])Hson[u]=v;
	}
}
void dfs2(int u,int Top){
	dfn[u]=++dfc;Hd[u]=Top;ifn[dfc]=u;
	if(!Hson[u])return;dfs2(Hson[u],Top);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==Fa[u]||v==Hson[u])continue;
		dfs2(v,v);
	}
}
inline int LCA(int u,int v){
	if(u==v)return u;
	while(Hd[u]!=Hd[v]){
		if(dep[Hd[u]]<dep[Hd[v]])swap(u,v);
		u=Fa[Hd[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	return v;
}
struct OP{int type,xx,l,r,k;}O[maxn<<1];
inline bool cmpl(OP A,OP B){return A.l<B.l;}
inline bool cmpr(OP A,OP B){return A.r>B.r;}
int ans[maxn],cntO;
int stk[maxn],top;
struct SegmentTree{
	int mx[maxn<<2];
	int pos[maxn];
	void build(int p,int L,int R){
		if(L>=R){pos[L]=p;return;}
		int mid=(L+R)>>1;
		build(p<<1,L,mid);build(p<<1|1,mid+1,R);
	}
	void Set(int inx,int xx){
		inx=pos[inx];
		mx[inx]=xx;
		for(inx>>=1;inx;inx>>=1)mx[inx]=max(mx[inx<<1],mx[inx<<1|1]);
	}
	void Add(int inx,int xx){
		inx=pos[inx];
		mx[inx]=max(mx[inx],xx);
		for(inx>>=1;inx;inx>>=1)mx[inx]=max(mx[inx<<1],mx[inx<<1|1]);
	}
	int Query(int p,int L,int R,int ql,int qr){
		if(ql<=L&&R<=qr)return mx[p];
		int mid=(L+R)>>1,ret=-inf;
		if(ql<=mid)ret=max(ret,Query(p<<1,L,mid,ql,qr));
		if(mid+1<=qr)ret=max(ret,Query(p<<1|1,mid+1,R,ql,qr));
		return ret;
	}
}SEG;
void solve(int L,int R){
	if(L>=R)return;
	int mid=(L+R)>>1;
	solve(L,mid);solve(mid+1,R);
	sort(O+L,O+mid+1,cmpr);
	sort(O+mid+1,O+R+1,cmpr);
	int p=L;
	for(int i=mid+1;i<=R;i++){
		while(p<=mid&&O[p].r>=O[i].r){
			if(O[p].type==1)SEG.Add(O[p].k,O[p].xx);
			--p;
		}
		if(O[i].type==0)ans[O[i].xx]=max(ans[O[i].xx],SEG.Query(1,1,N,O[i].k,N));
	}
	while(p>L){
		--p;
		if(O[p].type==1)SEG.Set(O[p].k,-inf);
	}
}
int main(){
//	freopen("query2.in","r",stdin);
//	freopen("query.out","w",stdout); 
	scanf("%d",&N);
	if(N==1){scanf("%d",&Q);while(Q--){int l,r,k;scanf("%d %d %d",&l,&r,&k);printf("1\n");}return 0;}
	for(int i=1,u,v;i<N;i++)scanf("%d %d",&u,&v),AddEdge(u,v),AddEdge(v,u);
	dfs1(1,0);dfs2(1,1);
	SEG.build(1,1,N);
	for(int i=1;i<=N;i++)SEG.Set(i,dep[i]);
	for(int i=1;i<N;i++){
		O[i].type=1;
		O[i].xx=dep[LCA(i,i+1)];
		O[i].l=i;
		O[i].r=i+1;
	}
	for(int i=1;i<N;i++){
		while(top&&O[stk[top]].xx>=O[i].xx)--top;
		if(!top)O[i].l=1;
		else O[i].l=stk[top]+1;
		stk[++top]=i;
	}
	top=0;
	for(int i=N-1;i>=1;i--){
		while(top&&O[stk[top]].xx>=O[i].xx)--top;
		if(!top)O[i].r=N;
		else O[i].r=stk[top];
		stk[++top]=i;
	}
	for(int i=1;i<=N-1;i++)O[i].k=O[i].r-O[i].l+1;
	cntO=N-1;
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++){
		int l,r,k;scanf("%d %d %d",&l,&r,&k);
		if(k==1){ans[i]=(l==r?dep[l]:SEG.Query(1,1,N,l,r));continue;}
		++cntO;
		O[cntO].type=0;
		O[cntO].xx=i;
		O[cntO].l=r-k+1;
		O[cntO].r=l+k-1;
		O[cntO].k=k;
	}
	for(int i=1;i<=N;i++)SEG.Set(i,-inf);
	sort(O+1,O+cntO+1,cmpl);
	solve(1,cntO);
	for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
	return 0;
}