Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<int>ed[200009];
int dst[200009],pr[200009][22],lvl[200009];
void dfs(int x,int p)
{
    lvl[x]=lvl[p]+1;
    pr[x][0]=p;
    for(int i=0;i<ed[x].size();i++)
        if(ed[x][i]!=p)dfs(ed[x][i],x);

}
int lca(int x,int y)
{
    if(lvl[x]<lvl[y])swap(x,y);
    int dst =lvl[x]-lvl[y];
    for(int i=0;i<=20;i++)
        if(dst&(1<<i))x=pr[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
    if(pr[x][i]!=pr[y][i]){x=pr[x][i];y=pr[y][i];}
    return pr[x][0];
}
int d(int x,int y)
{
    return lvl[x]+lvl[y]-2*lvl[lca(x,y)];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    memset(dst,-1,sizeof dst);
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        ed[x].push_back(i);
        ed[i].push_back(x);
    }
    dfs(1,0);
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
        pr[i][j]=pr[pr[i][j-1]][j-1];
    queue<int>q;
    for(int i=1;i<=n;i++)
    if(ed[i].size()>2){dst[i]=0;q.push(i);}
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<ed[u].size();i++)
        if(dst[ed[u][i]]==-1){dst[ed[u][i]]=dst[u]+1;q.push(ed[u][i]);}

    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        if(x==y){cout<<"yes"<<endl;continue;}
        if(ed[y].size()>1){cout<<"yes"<<endl;continue;}
        int r=d(x,y);
        if((dst[y]!=-1) &&r>2*dst[y]){cout<<"yes"<<endl;continue;}
        cout<<"no"<<endl;
    }


}
Copy
Escape from TarkZoo Kaitokid
GNU G++17
204 ms
22.7 MB
Accepted