第三个样例一直过不了，求调，cdq分治做法

#include<bits/stdc++.h>
using namespace std;
int q,n,head[500005],tot,cnt,dep[500005],f[500005],st[500005][25],st1[500005][25],dfn[500005],id[500005],num,c[500005],r[500005],ans[500005],b[500005];
struct sd{
	int ne,to;
}edge[1000005];
struct sp{
	int l,r,len,id,v;
}a[1000005];
void add(int x,int y){
	edge[++tot].ne=head[x];
	edge[tot].to=y;
	head[x]=tot;
} 
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
//	printf("%d %d\n",x,dep[x]);
	dfn[x]=++num;
	f[x]=fa;
	id[num]=x;
	for(int i=head[x];i;i=edge[i].ne){
		int y=edge[i].to;
		if(y==fa)	continue;
		dfs(y,x);
	}
	r[x]=num;
}
int get(int x,int y){
	if(dep[x]<dep[y])	return x;
	return y;
}
void pre(){
	for(int i=1;i<=num;i++)	st[i][0]=id[i];
	int t=log(num)/log(2)+1;
	for(int j=1;j<=t;j++){
		for(int i=1;i<=num-(1<<j)+1;i++){
			st[i][j]=get(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;i++)	st1[i][0]=dep[i];
	t=log(n)/log(2)+1;
	for(int j=1;j<=t;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
		}
	}
}
int getlca(int x,int y){
	if(dfn[x]>dfn[y])	swap(x,y);
	if(r[x]>=r[y])	return x;
	int t=log(dfn[y]-dfn[x]+1)/log(2);
	return f[get(st[dfn[x]][t],st[dfn[y]-(1<<t)+1][t])];
}
int lowbit(int x){
	return x&(-x);
}
void add1(int x,int v){
	if(!x)	return ;
	for(;x;x-=lowbit(x))	c[x]=max(c[x],v);
}
int ask(int x){
	if(!x)	return 0; 
	int res=0;
	for(;x<=n;x+=lowbit(x))	res=max(res,c[x]);
	return res;
}
void del(int x){
	if(!x)	return ;
	for(;x;x-=lowbit(x))	c[x]=0;
}
bool cmp(sp x,sp y){
	if(x.l==y.l && x.r==y.r)	return x.len>y.len; 
	if(x.l==y.l)	return x.r>y.r;
	return x.l>y.l;
}
bool cmp1(sp x,sp y){
	if(x.r==y.r)	return x.len>y.len; 
	return x.r>y.r;
}
void cdq(int l,int r){
	if(l>=r)	return ;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	int ll=l,rr=mid+1;
	for(;rr<=r;rr++){
		while(ll<=mid && a[ll].r>=a[rr].r){
			if(!a[ll].id)add1(a[ll].len,a[ll].v);
			ll++;
		}
		if(a[rr].id)ans[a[rr].id]=max(ans[a[rr].id],ask(a[rr].len));
//		printf("%d %d\n",rr,r);
//		printf("%d ",ll);
	}
//	printf("%d ",rr);
	for(int i=l;i<ll;i++){
		if(!a[i].id)	del(a[i].len);
	}
	sort(a+l,a+r+1,cmp1);
//	printf("%d %d\n",l,r);
//	for(int i=1;i<=q;i++)	printf("%d ",ans[i]);
//	printf("\n");
}
int rmq(int l,int r){
	int t=log(r-l+1)/log(2);
	return max(st1[l][t],st1[r-(1<<t)+1][t]);
}
int main(){
//	freopen("query3.in","r",stdin);
//	freopen("query.out","w",stdout); 
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	pre();
	for(int i=1;i<n;i++)	b[i]=getlca(i,i+1);//,printf("%d ",b[i]);
	stack<int>	stk;
	stk.push(0);
	for(int i=1;i<n;i++){
		while(stk.size() && dep[b[stk.top()]]>=dep[b[i]])	stk.pop();
		a[i].l=-stk.top()-1;
		stk.push(i);
	}
	while(stk.size())	stk.pop();
	stk.push(n);
	for(int i=n-1;i>=1;i--){
		while(stk.size() && dep[b[stk.top()]]>=dep[b[i]])	stk.pop();
		a[i].r=stk.top();
		a[i].len=a[i].r+a[i].l;
		a[i].id=0;
		a[i].v=dep[b[i]];
		stk.push(i);
//		printf("%d %d %d %d\n",a[i].l,a[i].r,i,dep[i]);
	}
//	printf("1");
	scanf("%d",&q);
	cnt=n-1;
	for(int i=1;i<=q;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		if(k!=1)	a[++cnt]={k-r-1,l+k-1,k-1,i,0};
		else{
			if(l==r)	ans[i]=dep[l];
			else	ans[i]=rmq(l,r);
		}
	}
//	memset(ans,0x3f,sizeof(ans));
	sort(a+1,a+cnt+1,cmp);
//	for(int i=1;i<=cnt;i++){
//		printf("%d %d %d %d %d\n",a[i].l,a[i].r,a[i].len,a[i].id,a[i].v);
//	}
	cdq(1,cnt);
	for(int i=1;i<=q;i++)	printf("%d\n",ans[i]);
}