时间复杂度求问

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int maxn=5e5+3;
int inline read(){
	int res=0;
	char c;c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
int n,q;
int first[maxn],nxt[maxn<<1],to[maxn<<1],tot;
void add(int x,int y){
	nxt[++tot]=first[x];first[x]=tot;to[tot]=y;
}
int dep[maxn],f[maxn][21];
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=1;i<=20;i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=first[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		f[v][0]=u;
		dfs(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];y=f[y][i];
		}
	}
	return f[x][0];
}
int t[maxn<<2];
void pushup(int u){
	t[u]=lca(t[u<<1],t[u<<1|1]);
}
void build(int u,int l,int r){
	if(l==r){
		t[u]=l;
		return;
	}
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pushup(u);
}
int find(int u,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		return t[u];
	}
	int res=0;
	if(x<=mid)res=find(u<<1,l,mid,x,y);
	if(y>mid){
		if(res)res=lca(res,find(u<<1|1,mid+1,r,x,y));
		else res=find(u<<1|1,mid+1,r,x,y);
	}
	return res;
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u,v;
		u=read();v=read();
		add(u,v);add(v,u);
	}
	dfs(1,0);
	build(1,1,n);
	cin>>q;
	for(int i=1;i<=q;i++){
		int l,r,k;
		l=read();r=read();k=read();
		int ans=0;
		for(int j=l;j+k-1<=r;j++){
			ans=max(ans,dep[find(1,1,n,j,j+k-1)]);
		}
		cout<<ans<<endl;
	}
	return 0;
}