#include<bits/stdc++.h>
using namespace std;
char ib[1<<24],*ip1=ib,*ip2=ib;
#define gc() (ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++)
inline int read(){
int x=0;char c=gc();
while(c<'0'||c>'9')c=gc();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
return x;
}
char ob[1<<24],*op=ob;
inline void pc(char c){
*op++=c;
}
void write(int x){
if(x>=10)write(x/10);
pc(x%10+'0');
}
void final_write(){
fwrite(ob,op-ob,1,stdout);
}
vector<int>g[500005];
int fa[19][500005],dep[500005];
void dfs(int x,int la){
for(auto cu:g[x]){
if(cu==la)continue;
dep[cu]=dep[x]+1;fa[0][cu]=x;
dfs(cu,x);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=18;i>=0;--i)if(dep[x]-dep[y]>=(1<<i))x=fa[i][x];
if(x==y)return x;
for(int i=18;i>=0;--i)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
namespace easy{
int sm[2000005];
void build(int l,int r,int o){
if(l==r){
sm[o]=dep[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid+1,r,o<<1|1);
sm[o]=max(sm[o<<1],sm[o<<1|1]);
}
int query(int l,int r,int o,int ll,int rr){
if(l>=ll&&r<=rr)return sm[o];
int mid=(l+r)>>1,ans=0;
if(mid>=ll)ans=max(ans,query(l,mid,o<<1,ll,rr));
if(mid<rr)ans=max(ans,query(mid+1,r,o<<1|1,ll,rr));
return ans;
}
}
int n,d[500005],l[500005],r[500005],k[500005];
int A[500005],B[500005],C[500005],ans[500005];
int u[500005],v[500005],st[500005],tt=0;
vector<int>gg[500005],g2[500005];
struct apple{
int x,z;
apple(int x=0,int z=0):x(x),z(z){}
bool operator<(const apple &other)const{
return x<other.x;
}
};
int c[500005];
inline void add(int x,int s){
while(x<=n&&c[x]<s)c[x]=s,x+=x&-x;
}
inline void clr(int x){
if(c[x])while(x<=n)c[x]=0,x+=x&-x;
}
inline int query(int x){
int ans=0;
while(x)ans=max(ans,c[x]),x-=x&-x;
return ans;
}
vector<apple>kj;
pair<vector<apple>,vector<apple>>solve(int l,int r){
if(l==r){
vector<apple>gl(g2[l].size()),gr(gg[l].size());
int zl=0,zr=0;
for(auto x:gg[l]){
gr[zr++]=apple(B[x],x);
}
for(auto x:g2[l]){
gl[zl++]=apple(v[x],x);
}
sort(gl.begin(),gl.end());
sort(gr.begin(),gr.end());
return make_pair(gl,gr);
}
int mid=(l+r)>>1;
auto a1=solve(l,mid),a2=solve(mid+1,r);
auto gl1=a1.first,g1=a1.second;
auto gl2=a2.first,g2=a2.second;
int sl1=gl1.size(),sl2=gl2.size();
int s1=g1.size(),s2=g2.size();
int w=0;
for(int i=0;i<sl1;++i){
while(w<s2&&g2[w].x<gl1[i].x){
int j=g2[w++].z;
ans[j]=max(ans[j],query(C[j]));
}
int j=gl1[i].z;
add(u[j]+v[j],d[j]);
}
while(w<s2){
int j=g2[w++].z;
ans[j]=max(ans[j],query(C[j]));
}
for(int i=0;i<sl1;++i){
int j=gl1[i].z;
clr(u[j]+v[j]);
}
if(l==1&&r==n){
return make_pair(kj,kj);
}
vector<apple>gl(sl1+sl2);
merge(gl1.begin(),gl1.end(),gl2.begin(),gl2.end(),gl.begin());
vector<apple>g(s1+s2);
merge(g1.begin(),g1.end(),g2.begin(),g2.end(),g.begin());
return make_pair(gl,g);
}
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dep[1]=1;dfs(1,0);
for(int i=1;i<=18;++i)for(int j=1;j<=n;++j)
fa[i][j]=fa[i-1][fa[i-1][j]];
for(int i=1;i<n;++i){
d[i]=dep[lca(i,i+1)];
}
easy::build(1,n,1);
for(int i=1;i<=n-1;++i){
while(tt&&d[st[tt]]>=d[i])--tt;
if(!tt)u[i]=1;
else u[i]=st[tt]+1;
st[++tt]=i;
}
tt=0;
for(int i=n-1;i>=1;--i){
while(tt&&d[st[tt]]>=d[i])--tt;
if(!tt)v[i]=n-1;
else v[i]=st[tt]-1;
v[i]=n-v[i];
g2[u[i]].emplace_back(i);
st[++tt]=i;
}
int q=read();
for(int i=1;i<=q;++i){
l[i]=read(),r[i]=read(),k[i]=read();
if(k[i]==1){
ans[i]=easy::query(1,n,1,l[i],r[i]);
continue;
}
--r[i];--k[i];
A[i]=max(1,r[i]-k[i]+1)+1;
B[i]=n-min(n-1,k[i]+l[i]-1);
C[i]=n-k[i]+1;
gg[A[i]].emplace_back(i);
}
solve(1,n);
for(int i=1;i<=q;++i)write(ans[i]),pc('\n');
final_write();
return 0;
}
SD-0744
京公网安备 11011102002149号