如果这是违规的就删了吧。毕竟这连讨论区题解都算不上。

居然有人说这题数据强，那我必须要出来说道两句了。

以下是我的考场代码，复杂度 $O(nq \log n)$，在官方数据中获得了 $100$ 分的好成绩，洛谷上最慢的测试点只跑了 1.3s。一条倒着的链就能让它升天。

暴力过题就不往题解区放了，毕竟数据也没法面面俱到卡掉所有假做法，大家看个乐呵就好。

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N=500005;
const int LG=21;
const int sq=512;
int n,cc,Q,lim,idx,dep[N],fa[N],rev[N],dfn[N],st[LG][N],smn[LG][N],smx[LG][N],A[N],B[N],C[N],ans[N],T[N<<2]; vector<int>g[N];
struct Qry{
	int l,r,x;
}q[N];
struct Edge{ int to,nxt; }e[N<<1]; int head[N],etot;
inline void ade(int u,int v){ e[++etot]={v,head[u]}; head[u]=etot; }
inline int dmn(int x,int y){ return dfn[x]<dfn[y]?x:y; }
inline int dmx(int x,int y){ return dfn[x]>dfn[y]?x:y; }
inline void dfs(int u){
	dfn[u]=++idx; rev[idx]=u; st[0][idx-1]=fa[u];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa[u]) continue;
		fa[v]=u; dep[v]=dep[u]+1; dfs(v);
	}
}
inline int lca(int x,int y){
	if(dfn[x]>dfn[y]) swap(x,y);
	if(dfn[x]==dfn[y]) return x;
	int k=__lg(dfn[y]-dfn[x]);
	return dmn(st[k][dfn[x]],st[k][dfn[y]-(1<<k)]);
}
struct Pr{int x,y;};
inline Pr qry(int l,int r){
	int k=__lg(r-l+1);
	return {dmn(smn[k][l],smn[k][r-(1<<k)+1]),dmx(smx[k][l],smx[k][r-(1<<k)+1])};
}
inline int brt(int l,int r,int x){
	Pr now=qry(r,r+x-1); int ans=dep[lca(now.x,now.y)];
	while(1){
		int p=max(now.x,now.y)-1;
		if(p-x+1<l) break; r=p-x+1; now=qry(r,r+x-1);
		ans=max(ans,dep[lca(now.x,now.y)]);
	}	return ans;
}
inline void build(int u,int l,int r){
	if(l==r) return T[u]=C[l],void();
	int mid=l+r>>1;
	build(ls(u),l,mid); build(rs(u),mid+1,r); T[u]=max(T[ls(u)],T[rs(u)]);
}
inline void upd(int x,int y){
	int u=1,l=1,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(x<=mid) r=mid,u=ls(u);
		else l=mid+1,u=rs(u);
	}	T[u]=y;
	while(u>1)u>>=1,T[u]=max(T[ls(u)],T[rs(u)]);
}
inline int ask(int u,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return T[u];
	int mid=l+r>>1;
	if(qr<=mid) return ask(ls(u),l,mid,ql,qr);
	if(ql>mid) return ask(rs(u),mid+1,r,ql,qr);
	return max(ask(ls(u),l,mid,ql,qr),ask(rs(u),mid+1,r,ql,qr));
}
int main(){
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		ade(u,v); ade(v,u);
	}
	dep[1]=1; dfs(1);
	for(int j=1;(1<<j)<n;j++)
		for(int i=1;i+(1<<j)-1<n;i++)
			st[j][i]=dmn(st[j-1][i],st[j-1][i+(1<<j-1)]);
	for(int i=1;i<=n;i++) smn[0][i]=smx[0][i]=i;
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			smn[j][i]=dmn(smn[j-1][i],smn[j-1][i+(1<<j-1)]),smx[j][i]=dmx(smx[j-1][i],smx[j-1][i+(1<<j-1)]);
	cin>>Q;
	for(int i=1;i<=Q;i++)
		cin>>q[i].l>>q[i].r>>q[i].x,q[i].r=q[i].r-q[i].x+1;
	for(int i=1;i<=Q;i++){
		if(q[i].x>=sq||q[i].r-q[i].l+1<=sq) ans[i]=brt(q[i].l,q[i].r,q[i].x);
		else g[q[i].x].emplace_back(i),lim=max(lim,q[i].x);
	}
	for(int i=1;i<=n;i++) A[i]=B[i]=dfn[i],C[i]=dep[i];
	build(1,1,n);
	for(int j=1;j<=lim;j++){
		for(int i=1;i+j-1<=n;i++){
			int k=i+j-1;
			if(dfn[k]>=A[i]&&dfn[k]<=B[i]) continue;
			if(dfn[k]<A[i]) A[i]=dfn[k]; else B[i]=dfn[k];
			int t=dep[lca(rev[A[i]],rev[B[i]])];
			if(t!=C[i])C[i]=t,upd(i,C[i]);
		}
		for(int k:g[j]) ans[k]=ask(1,1,n,q[k].l,q[k].r);
	}
	for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
	return 0;
}