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

const int N = 2e5+5;

int P[N][20], lvl[N], W[N], last[N];
vector < int > adj[N];
void dfs(int i=1, int p = 0)
{
    last[i] = (adj[p].size() > 2 ? p : last[p]);
    W[i] = (adj[i].size() > 2 ? 1 : 0) + W[p];
    lvl[i] = lvl[p] + 1;
    P[i][0] = p;
    for(int j = 1 ; j < 18 ; j++) P[i][j] = P[P[i][j-1]][j-1];

    for(auto x : adj[i]) if(x != p)
        dfs(x, i);
}

int getLCA(int u, int v)
{
    if(lvl[u] < lvl[v]) swap(u,v);
    int dist = lvl[u] - lvl[v];
    for(int i = 0 ; i < 18 ; i++) if((dist>>i)&1) u = P[u][i];
    for(int i = 17 ; i >= 0 ; i--) if(P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
    return u == v ? u : P[u][0];
}
int getKthPar(int u, int k)
{
    for(int i = 0 ; i < 17 ; i++) if((k>>i)&1)
        u = P[u][i];
    return u;
}
int getW(int ch, int pr)
{
    return W[ch] - W[P[pr][0]];
}
int getDist(int u, int v)
{
    return lvl[u] + lvl[v] - 2*lvl[getLCA(u, v)];
}
int main()
{
    ios::sync_with_stdio(false);    cin.tie(NULL);  cout.tie(NULL);
    int n, q;
    cin >> n >> q;
    for(int i = 2 ; i <= n ; i++)
    {
        int x;  cin >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    dfs(1);

    while(q--)
    {

        int a, b;   cin >> a >> b;
        if(a == b || adj[b].size() > 1)
        {
            cout << "yes\n";
            continue;
        }

        int dist = getDist(a, b);
        int bdist = 0;
        if(dist == 1)
        {
            cout << "no\n";
            continue;
        }


        int lca = getLCA(a, b);

        if(getW(b, lca) - (adj[b].size() > 2 ? 1 : 0) > 0)
        {
            bdist = getDist(last[b],b);
        }
        else if(getW(a, lca) - (adj[a].size() > 2 ? 1 : 0) > 0)
        {
            int a = P[a][0];
            int v = getW(a, lca);
            int u = a;
            for(int i = 17 ; i >= 0 ; i--) if(getW(a, P[u][i]) < v)
                u = P[u][i];
            if(u != lca)
                u = P[u][0];
            bdist = getDist(u, b);
        }
        else bdist = 1e7;

        if(bdist < (dist+1)/2)
        {
            cout << "yes\n";
            continue;
        }
        else
        {
            cout << "no\n";
            continue;
        }

    }
}
Copy
Escape from TarkZoo EsmaelSufe
GNU G++17
3 ms
5.2 MB
Runtime Error