提出 #46652533

---

ソースコード 拡げる

// LUOGU_RID: 129708034
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
void write(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int n,tot,mx,d1,d2;
int to[2*N],nxt[2*N],head[N];
void add(int u,int v)
{
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
    return;
}
void dfs(int id,int fat,int dis)
{
    if(dis>mx)
    {
        mx=dis;
        d1=id;
    }
    for(int i=head[id];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=fat)
        {
            dfs(v,id,dis+1);
        }
    }
    return;
}
bool book[N];
stack <int> q;
void dfs2(int id,int fat,int dis)
{
    if(dis>mx)
    {
        mx=dis;
        d2=id;
    }
    for(int i=head[id];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=fat)
        {
            dfs2(v,id,dis+1);
        }
    }
    return;
}
bool b;
void dfs3(int id,int fat)
{
    //cout<<id<<" "<<fat<<endl; 
    if(id==d2)
    {
        b=1;
        return;
    }
    for(int i=head[id];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=fat)
        {
            q.push(v);
            book[v]=1;
            dfs3(v,id);
            if(!b)
            {
                q.pop();
                book[v]=0;
            }
            else
            {
                break;
            }
        }
    }
    return;
}
int zj[N],len;
int gs[N],dep[N],fa[N];
void dfsz(int id,int dis,int fat,int zdd)
{
    dep[id]=dis;
    gs[id]=zdd;
    fa[id]=fat;
    for(int i=head[id];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=fat && !book[v])
        {
            dfsz(v,dis+1,id,zdd);
        }
    }
    return;
}
int mxjl[N],awa[N];
int m;
int main()
{
    // freopen("intoxicated.in","r",stdin);
    // freopen("intoxicated.out","w",stdout);
    n=read();
    for(int u,v,i=1;i<n;i++)
    {
        u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs(1,0,0);
    mx=0;
    book[d1]=1;
    dfs2(d1,0,0);
    dfs3(d1,0);
    //cout<<d1<<" "<<d2<<endl;
    q.pop();
    zj[++len]=d2;
    while(!q.empty())
    {
        int a=q.top();
        q.pop();
        zj[++len]=a;
        //cout<<a<<endl;
    }
    zj[++len]=d1;
    //cout<<len<<endl; 
    //cout<<d1<<" "<<d2<<endl;
    for(int i=1;i<=len;i++)
    {
        int dq=zj[i];
        mxjl[i]=max(i-1,len-i);
        awa[dq]=i;
       // cout<<dq<<" ";
        dfsz(dq,0,0,dq);
    }
    // cout<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dep[i]<<" "<<gs[i]<<endl;
    // }
    m=read();
    int x,d;
    while(m--)
    {
        x=read(),d=read();
        int ans=dep[x]+mxjl[awa[gs[x]]];
        //cout<<dep[x]<<" "<<mxjl[gs[awa[x]]]<<" "<<gs[awa[x]]<<" "<<awa[x]<<" "<<ans<<endl;
        if(ans<d)
        {
            puts("-1");
        }
        else
        {
            if(dep[x]>=d)
            {
                int pd=x;
                for(int i=1;i<=d;i++)
                {
                    pd=fa[pd];
                }
                write(pd);
                puts("");
            }
            else
            {
            int xy=d-dep[x];
            if(awa[gs[x]]-1<xy)
            {
                write(zj[awa[gs[x]]+xy]);
                puts("");
            }
            else
            {  
                write(zj[awa[gs[x]]-xy]);
                puts("");
            }
            }
        }
    }
    return 0;
}

提出情報

ジャッジ結果