复杂度应该是 $O(n^2\log n)$ 来着，为什么不能拿 20 pts，是我写假了吗？

vector<int>e[50005];
int n,q,dep[50005],fa[50005][25],l,r,k,lg[50005];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=lg[dep[u]];i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=0;i<e[u].size();i++){
		if(e[u][i]==f)continue;
		dfs(e[u][i],u);
	}
}
int LCA(int x,int y){
	if(x==1||y==1)return 1;
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y]){
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y)return x;
	for(int i=lg[dep[x]]-1;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
//	freopen("query.in","r",stdin);
//	freopen("query.out","w",stdout);
	for(int i=1;i<=5e4;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	n=read();
	for(int u,v,i=1;i<n;i++){
		u=read();v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	q=read();
	while(q--){
		l=read();r=read();k=read();
		int ans=0,lca=0;
		for(int i=l;i<=max(l,r-k+1);i++){
			lca=0;
			if(k==1)ans=max(ans,dep[i]);
			else{
			for(int j=i;j<i+k;j++){
				if(lca==0)lca=j;
				else lca=LCA(lca,j);
			}ans=max(ans,dep[lca]);}
		}
		write(ans);
		puts("");
	}
	return 0;
}