求助帮忙卡常

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define boo(i) bitset<i>
#define ri register int
#define rll register long long
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define max_(i,j) ((i)<(j)?(j):(i))
#define min_(i,j) (i<j?i:j)
#define abs_(x) (x>0?x:(-x))
using namespace std;
const int MAXN=5e5+5;
int fat[MAXN][21];
vector<int>ed[MAXN];
int n;
#define lc (x<<1)
#define rc (x<<1|1)
struct poi{
	int x;
	int ls,rs;
	int siz;
};
poi t;
#define maxx(x,y,z) ((x)>(y)?(max_(x,z)):(max_(y,z)))
inline poi merg(poi x,poi y){
	
	t.x=maxx(x.x,y.x,x.rs+y.ls);
	t.ls=x.ls;
	if(x.siz==x.x){
		t.ls=x.siz+y.ls;
	}
	t.rs=y.rs;
	if(y.siz==y.x){
		t.rs=y.siz+x.rs;
	}
	t.siz=x.siz+y.siz;
	return t;
}
const int N=2e6+5;
poi xlr;
struct SEG{
	int maxn[N],pos[N];
	int ls[N],rs[N];
	int pl[N],pr[N];
	void buil(int x,int l,int r){
		pl[x]=l;pr[x]=r;
		if(l==r){
			pos[l]=x;
			return;
		}
		int mid=(l+r)>>1;
		buil(x<<1,l,mid);
		buil(x<<1|1,mid+1,r);
	}
	int mid;
	inline void push_up(int x){
		mid=(pl[x]+pr[x])>>1;
		maxn[x]=maxx(maxn[lc],maxn[rc],rs[lc]+ls[rc]);
		ls[x]=ls[lc];
		if(maxn[lc]==mid-pl[x]+1){
			ls[x]=mid-pl[x]+1+ls[rc];
		}
		rs[x]=rs[rc];
		if(maxn[rc]==pr[x]-mid){
			rs[x]=pr[x]-mid+rs[lc];
		}
	}
	inline void upd(int x,int p,int v){
		int now=pos[p];
		maxn[now]=ls[now]=rs[now]=v;
		do{
			now=(now>>1);
			push_up(now);
		}while(now^1);
	}
	inline void que(int x,int ql,int qr){
		ql=pos[ql]-1;
		qr=pos[qr]+1;
		poi cxt={0,0,0,0};
		int ql1,qr1;
		for(;ql^qr^1;ql>>=1,qr>>=1){
			if(~ql&1){
				ql1=ql^1;
				xlr=merg(xlr,(poi){maxn[ql1],ls[ql1],rs[ql1],pr[ql1]-pl[ql1]+1});
			}
			if(qr&1){
				qr1=qr^1;
				cxt=merg((poi){maxn[qr1],ls[qr1],rs[qr1],pr[qr1]-pl[qr1]+1},cxt);
			}
		}
		xlr=merg(xlr,cxt);
	}
}scz;
int dep[MAXN];
int sta[MAXN],staf[MAXN],len;
void dfs(int x,int fa){
	fat[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=1;i<=20;i++){
		fat[x][i]=fat[fat[x][i-1]][i-1];
	}
	for(int i=0;i<ed[x].size();i++){
		if(ed[x][i]==fa){
			continue;
		}
		len++;sta[len]=ed[x][i];staf[len]=x;
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(int i=20;i>=0;i--){
		if(dep[fat[x][i]]>=dep[y]){
			x=fat[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=20;i>=0;i--){
		if(fat[x][i]!=fat[y][i]){
			x=fat[x][i];
			y=fat[y][i];
		}
	}
	return fat[x][0];
}
int ans[MAXN];
int que[MAXN],tque[MAXN];
int val[MAXN];
vector<int>pos[MAXN];
struct quer{
	int l,r,k;
}a[MAXN];
void ef(int ql,int qr,int l,int r){
	if(ql>qr){
		return ;
	}
	if(l==r){
		for(int i=ql;i<=qr;i++){
			ans[que[i]]=l;
		}
		return;
	}
	int mid=(l+r+1)>>1;
	for(int i=mid;i<=r;i++){
		for(int j=0;j<pos[i].size();j++){
			scz.upd(1,pos[i][j],1);
		}
	}
	int cl=ql-1,cr=qr+1;
	for(int i=ql;i<=qr;i++){
		xlr=(poi){0,0,0,0};scz.que(1,a[que[i]].l,a[que[i]].r);
		if(xlr.x>=a[que[i]].k-1){
			cr--;
			tque[cr]=que[i];
		}else{
			cl++;
			tque[cl]=que[i];
		}
	}
	for(int i=ql;i<=qr;i++){
		que[i]=tque[i];
	}
	ef(ql,cl,l,mid-1);
	for(int i=mid;i<=r;i++){
		for(int j=0;j<pos[i].size();j++){
			scz.upd(1,pos[i][j],0);
		}
	}
	ef(cr,qr,mid,r);
}
int maxd;
struct stm{
	int st[MAXN][21];
	int que(int l,int r){
		int siz=log2(r-l+1);
		return max(st[l][siz],st[r-(1<<siz)+1][siz]);
	}
	void init(){
		for(int i=1;i<=n;i++){
			st[i][0]=dep[i];
		}
		for(int i=1;i<=20;i++){
			for(int j=1;j<=n-(1<<i)+1;j++){
				st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
			}
		}
	}
}kly;
int read(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int main(){
	n=read();
	for(int i=1,x,y;i<n;i++){
		x=read();y=read();
		ed[x].push_back(y);
		ed[y].push_back(x);
	}
	len=1;
	sta[len]=1;
	while(len){
		int t1=sta[len],t2=staf[len];len--;
		dfs(t1,t2);
	}
	int tt=log2(n)+1;
	scz.buil(1,1,(1<<tt));
	for(int i=2;i<=n;i++){
		val[i]=dep[lca(i-1,i)];
		pos[val[i]].push_back(i);
		maxd=max(maxd,dep[lca(i,i-1)]);
	}
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		a[i].l=read();a[i].r=read();a[i].k=read();
		a[i].l++;
		que[i]=i;
	}
	kly.init();
	ef(1,q,1,maxd);
	for(int i=1;i<=q;i++){
		if(a[i].k==1){
			ans[i]=kly.que(a[i].l-1,a[i].r);
		}
		printf("%d\n",ans[i]);
	}
}