一个点T了,求助
查看原帖
一个点T了,求助
456675
a_sad_soul楼主2023/7/11 17:02
#include<bits/stdc++.h>
#define MAXN 5000006
using namespace std;
int dp[MAXN];
int dep[MAXN],maxdep=1;
struct node{
    int to;
    node *next;
}*head[MAXN],*tmp;
void add(int u,int v)
{
    tmp=new node;
    tmp->to=v;
    tmp->next=head[u];
    head[u]=tmp;
}
bool vis[MAXN];
int f[MAXN];
void dfs(int u)
{
    vis[u]=1;
    for(node *i=head[u];i!=NULL;i=i->next)
    {
        int v=i->to;
        dep[v]=dep[u]+1;
        f[v]=u;
        if(!dp[dep[v]])dp[dep[v]]=v;
        else while(!vis[dp[dep[v]]])dp[dep[v]]=f[dp[dep[v]]];
        dfs(v);
    }
    vis[u]=0;
}
int n,m;
int read()
{
    char ch=0;
    int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x;
}
void write(int x)
{
   // int tot=0;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
        int u=read();
        add(u,i);
    }
    dep[1]=1;
    dfs(1);
    dp[1]=1;
    for(int i=1;i<=m;++i)
    {
        int k=read();

        write(dp[k]);
        putchar('\n');
    }
    return 0;
}
2023/7/11 17:02
加载中...