這個也是寫給自己看的。

首先可以看每一種答案取到的范圍。

然后就是兩個區間求交的長度會大于等于 k。

這個比較好求。

稍微有點難的部分就是他的答案區間被我的目標區間包含。

這個我一開始在考場上寫的是 cdq，然后沒寫完。

但是我現在會了一個更簡單的做法。

就是直接按照長度排序就行了。

這題有點卡常，貼卡常之前的代碼吧，比較好看。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define gt(x,y) get<y>(x)
#define N 500010
int n,q,dep[N],f[N][20],st[N][20],lg[N],ans[N],maxn[N][20];
struct stu{int l,r,v;}ad[N],ask[N];
vector<int>to[N];
vector<pair<int,int>>guil[N],guir[N],guik[N],gual[N],guar[N];
vector<tuple<int,int,int>>guak[N];
inline void init(int x,int fa){
	dep[x]=dep[fa]+1;f[x][0]=fa;rep(i,1,19){f[x][i]=f[f[x][i-1]][i-1];}
	for(int y:to[x]){if(y==fa){continue;}init(y,x);}
}
inline int lca(int x,int y){
	if(x==y){return x;}if(dep[x]<dep[y]){swap(x,y);}
	per(i,19,0){if(dep[f[x][i]]>=dep[y]){x=f[x][i];}}if(x==y){return x;}
	per(i,19,0){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
inline int LCA(int l,int r){if(l==r){return l;}r--;int k=lg[r-l+1];return lca(st[l][k],st[r-(1<<k)+1][k]);}
inline int spj(int l,int r){int k=lg[r-l+1];return max(maxn[l][k],maxn[r-(1<<k)+1][k]);}
struct su{int l,r,maxn;};
struct segtree{
	su t[N<<2];
	#define ls p<<1
	#define rs p<<1|1
	void build(int p,int l,int r){
		t[p].l=l;t[p].r=r;t[p].maxn=0;
		if(l==r){return;}int mid=(l+r)>>1;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void clr(int p){t[p].maxn=0;if(t[p].l==t[p].r){return;}clr(ls);clr(rs);}
	void update(int p,int x,int k){
		if(t[p].l==t[p].r){t[p].maxn=max(t[p].maxn,k);return;}
		if(x<=t[ls].r){update(ls,x,k);}else{update(rs,x,k);}
		t[p].maxn=max(t[ls].maxn,t[rs].maxn);
	}
	int ask(int p,int l,int r){
		if(l>r){return 0;}
		if(l<=t[p].l&&t[p].r<=r){return t[p].maxn;}
		int maxn=0;
		if(l<=t[ls].r){maxn=max(maxn,ask(ls,l,r));}
		if(r>=t[rs].l){maxn=max(maxn,ask(rs,l,r));}
		return maxn;
	}
	#undef ls
	#undef rs
}mst;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;rep(i,1,n-1){int u,v;cin>>u>>v;to[u].push_back(v);to[v].push_back(u);}
	init(1,0);rep(i,1,n-1){st[i][0]=lca(i,i+1);}lg[0]=-1;rep(i,1,n){lg[i]=lg[i>>1]+1;}
	rep(j,1,19){rep(i,1,n-(1<<j)){st[i][j]=lca(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}
	rep(i,1,n){maxn[i][0]=dep[i];}rep(j,1,19){rep(i,1,n-(1<<j)+1){maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);}}
	rep(i,1,n-1){
		int l=1,r=i,nd=lca(i,i+1);
		while(l<=r){
			int mid=(l+r)>>1;
			if(LCA(mid,i+1)==nd){ad[i].l=mid;r=mid-1;}
			else{l=mid+1;}
		}
		l=i+1;r=n;
		while(l<=r){
			int mid=(l+r)>>1;
			if(LCA(i,mid)==nd){ad[i].r=mid;l=mid+1;}
			else{r=mid-1;}
		}
		ad[i].v=dep[nd];
		guil[ad[i].l].push_back({ad[i].r,ad[i].v});
		guir[ad[i].r].push_back({ad[i].l,ad[i].v});
		guik[ad[i].r-ad[i].l+1].push_back({ad[i].r,ad[i].v});
	}
	cin>>q;
	rep(i,1,q){
		int l,r,k;cin>>l>>r>>k;ask[i].l=l;ask[i].r=r;ask[i].v=k;
		gual[l].push_back({k,i});
		guar[r].push_back({k,i});
		guak[k].push_back(make_tuple(l,r,i));
	}
	mst.build(1,1,n);
	rep(i,1,n){
		for(pair<int,int> p:guil[i]){mst.update(1,p.first,p.second);}
		for(pair<int,int> p:gual[i]){ans[p.second]=max(ans[p.second],mst.ask(1,i+p.first-1,n));}
	}
	mst.clr(1);
	per(i,n,1){
		for(pair<int,int> p:guir[i]){mst.update(1,p.first,p.second);}
		for(pair<int,int> p:guar[i]){ans[p.second]=max(ans[p.second],mst.ask(1,1,i-p.first+1));}
	}
	mst.clr(1);
	per(i,n,1){
		for(pair<int,int> p:guik[i]){mst.update(1,p.first,p.second);}
		for(tuple<int,int,int> tp:guak[i]){ans[gt(tp,2)]=max(ans[gt(tp,2)],mst.ask(1,gt(tp,0)+i-1,gt(tp,1)));}
	}
	rep(i,1,q){
		if(ask[i].v==1){cout<<spj(ask[i].l,ask[i].r)<<'\n';continue;}
		cout<<ans[i]<<'\n';
	}
	return 0;
}
/*
10
1 4
1 5
1 7
1 8
2 5
2 9
2 10
3 7
5 6
5
1 10 2
2 8 5
6 9 2
6 9 3
1 10 10
*/