比赛 2025.1.14 评测结果 AAAAATTTTTTTTAAATTTTTTTTT
题目名称 树上查询 最终得分 32
用户昵称 flyfree 运行时间 59.967 s
代码语言 C++ 内存使用 139.87 MiB
提交时间 2025-01-14 21:05:04
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 500010
#define inf 1e9
inline ll read(){
    ll x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
struct node_sgt{
    ll l[MAXN*4],r[MAXN*4],minz[MAXN*4];
    void push_up(ll now){
        minz[now]=min(minz[now*2],minz[now*2+1]);
    }
    void build(ll dl,ll dr,ll now){
        l[now]=dl,r[now]=dr,minz[now]=inf;
        if(dl==dr)return;
        ll mid=(dl+dr)/2;
        build(dl,mid,now*2);
        build(mid+1,dr,now*2+1);
    }
    ll find(ll dl,ll dr,ll now){
        if(l[now]>=dl&&r[now]<=dr){
            return minz[now];
        }
        ll mid=(l[now]+r[now])/2,ans=inf;
        if(dl<=mid)ans=min(ans,find(dl,dr,now*2));
        if(dr>mid)ans=min(ans,find(dl,dr,now*2+1));
        return ans; 
    }
    void insert(ll pos,ll val,ll now){
        minz[now]=min(minz[now],val);
        if(l[now]==r[now])return;
        ll mid=(l[now]+r[now])/2;
        if(pos<=mid)insert(pos,val,now*2);
        else insert(pos,val,now*2+1);
    }
}sgt;
ll fa[MAXN][50],dep[MAXN],v[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll n,q,idx;
void build(ll x,ll y){
    nxt[++idx]=hd[x];
    ed[idx]=y;
    hd[x]=idx;
}
void dfs(ll now,ll p){
    fa[now][0]=p;
    dep[now]=dep[p]+1;
    for(int i=1;i<=30;i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=hd[now];i;i=nxt[i]){
        ll y=ed[i];
        if(y==p)continue;
        dfs(y,now);
    }
}
ll lca(ll x,ll y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=30;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y]){
            x=fa[x][i];
        }
    }
    if(x==y)return x;
    for(int i=30;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);
    n=read();
    for(int i=1;i<n;i++){
        ll x=read(),y=read();
        build(x,y);
        build(y,x);
    }
    dfs(1,0);
    sgt.build(1,n-1,1);
    for(int i=1;i<n;i++){
        v[i]=dep[lca(i,i+1)];
        sgt.insert(i,v[i],1);
//        cout<<v[i]<<" ";
    }
//    cout<<endl;
    q=read();
    for(int i=1;i<=q;i++){
        ll l=read(),r=read(),k=read(),ans=-inf;
        if(k==1){
            for(int x=l;x<=r;x++)ans=max(ans,dep[x]);
        }else{
            for(int x=l;x+k-1<=r;x++){
                ll y=x+k-1;
                ans=max(ans,sgt.find(x,y-1,1));
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}