Military Problem

题意

你有一棵有个节点的树，有次询问，每次询问有，指从以为根的子树出发到达的第个点是哪一个？如果不存在（即，子树的大小小于），输出。

分析

很的一道题啊。你先预处理出每个点的序以及每个序对应的点和每棵子树的大小就可以了。
询问的时候输出就好了。（数组存的是每个点的序，数组存的是每个序对应的点）.

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+6,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,q,cnt,tot;
int head[N],siz[N],a[N],dfn[N],to[N];
struct node
{
    int nxt,to;
}e[N<<1];

inline int read()
{
    register 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<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void dfs(int x)
{
    a[++tot]=x;
    siz[x]=1;
    dfn[x]=tot;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        dfs(y);
        siz[x]+=siz[y];
    }
}

int main()
{
    n=read();q=read();
    for(int i=2;i<=n;i++) to[i]=read();
    for(int i=n;i>=2;i--)
        add(to[i],i);
    dfs(1);
//    for(int i=1;i<=n;i++)
//        printf("%d ",dfn[i]);
//    printf("\n");
    while(q--)
    {
        int u=read(),k=read();
        if(siz[u]<k)    printf("-1\n");
        else printf("%d\n",a[dfn[u]+k-1]);
    }
    return 0;
}

小提醒

如果使用链式前向星存边的话可以先全部读入，再倒序建边。这样才可以符合题意。