Source Code
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int,int>
#define F first
#define S second
#define ever (;;)

const int N = 200100;

bool isLeaf[N],has[N][20],good[N];
int n,sub[N],q,p[N][20],deep[N],in[N],out[N],timer;
vector <int> adj[N];

void DFS(int u,int par)
{
    p[u][0] = par;
    has[u][0] = good[u];
    deep[u] = 1+deep[par];
    in[u] = ++timer;
    sub[u] = 1;

    for(auto v:adj[u])
        if( v != par )
        {
            DFS(v,u);
            sub[u] += sub[v];
        }

    out[u] = timer;
}

int jump(int u,int k)
{
    for(int i=0; i<20; i++)
        if( k&(1<<i) )
            u=p[u][i];

    return u;
}

int get(int u,int k)
{
    bool ret = good[u];

    for(int i=0;i<20;i++)
    {
        if( k&(1<<i) )
        {
            ret |= has[u][i];
            u = p[u][i];
        }
    }

    return ret;
}

int LCA(int u,int v)
{
    if( u == v )return u;
    if( deep[u]<deep[v] )swap(u,v);

    int dif = deep[u]-deep[v];
    u=jump(u,dif);

    if( u == v )return u;

    for(int i=20-1; i>=0; i--)
        if( p[u][i]!=p[v][i] )
        {
            u = p[u][i];
            v = p[v][i];
        }

    return p[u][0];
}

int dis(int u,int v)
{
    return deep[u]+deep[v]-2*deep[LCA(u,v)];
}

int getOnPath(int a,int b,int moves)
{
    int lca = LCA(a,b);

    if( deep[a] - deep[lca] >= moves )
        return jump(a,moves);

    moves -= deep[a] - deep[lca];

    return jump(b,deep[b]-deep[lca]-moves);
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        adj[i].push_back(x);
        adj[x].push_back(i);
    }

    DFS(1,0);

    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++)
        {
            p[i][j] = p[ p[i][j-1] ][j-1];
            has[i][j] = ( has[ p[i][j-1] ][j-1] | has[i][j-1] );
        }

    for(int i=1;i<=n;i++)
    {
        isLeaf[i] = ( (int)(adj[i].size()) == 1 );
        good[i] = ( (int)(adj[i].size()) >= 3 );
    }

    while( q-- )
    {
        int a,b;
        scanf("%d%d",&a,&b);

        if( a == b || !isLeaf[b] )
        {
            printf("yes\n");
            continue;
        }

        int x = getOnPath(a,b,(dis(a,b)-1)/2);

        int lca = LCA(x,a);

        if( get(a,deep[a]-deep[lca]) || get(x,deep[x]-deep[lca]) )
            printf("yes\n");
        else
            printf("no\n");
    }
}
Copy
Escape from TarkZoo Naseem17
GNU G++17
30 ms
11.8 MB
Wrong Answer