Source Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.1415926535
#define fast ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef pair<ll,ll> pli;
typedef pair<int,int> pii;
typedef pair<ld,ld> pld;
ll MOD=1000000007 ;
ll MX=1000000000000000;

const int N=200200;
ll n,q;
vector<ll>adj[N];
ll p[N];

ll tin[N];
ll lev[N];
ll tout[N];
ll up[30][N];
ll sons[30][N];
ll sons2[30][N];
ll logn=19;
ll timer=0;
void dfs(int x,int p,int l)
{
    tin[x]=++timer;
    lev[x]=l;
    up[0][x]=p;
    if(adj[x].size()>1)
    {
        sons[0][x]=lev[x];
        sons2[0][x]=lev[x];
    }
    else
    {
        sons[0][x]=0;
        sons2[0][x]=MX;
    }
    for(int i=1;i<=logn;i++)
    {
        up[i][x]=up[i-1][up[i-1][x]];
        sons[i][x]=max(sons[i-1][x],sons[i-1][up[i-1][x]]);
        sons2[i][x]=min(sons2[i-1][x],sons2[i-1][up[i-1][x]]);
    }
    for(int i=0;i<adj[x].size();i++)
    {
        int nod=adj[x][i];
        if(nod!=p)
            dfs(nod,x,l+1);
    }
    tout[x]=++timer;
}
bool is_parent(int x,int y)
{
    return (tin[x]<=tin[y]&&tout[x]>=tout[y]);
}
int lca(int a,int b)
{
    if(is_parent(a,b))
        return a;
    if(is_parent(b,a))
        return b;
    for(int i=logn;i>=0;i--)
    {
        if(!is_parent(up[i][a],b))
        {
            a=up[i][a];
        }
    }
    return up[0][a];
}
ll nearest_sol(ll a,ll b)
{
    ll res=0;
    for(int i=logn;i>=0;i--)
    {
        if(!is_parent(up[i][a],b))
        {
            res=max(res,sons[i][a]);
            a=up[i][a];
        }
    }
    return res;
}
ll nearest_sol2(ll a,ll b)
{
    ll res=MX;
    for(int i=logn;i>=0;i--)
    {
        if(!is_parent(up[i][a],b))
        {
            res=min(res,sons2[i][a]);
            a=up[i][a];
        }
    }
    res=min(res,sons2[0][a]);
    return res;
}
ll dis(ll x,ll y)
{
    return lev[x]+lev[y]-2*lev[lca(x,y)];
}
int main()
{
    fast;
    //freopen("input.txt","r",stdin);
    cin>>n>>q;
    ll is_linear=1;
    for(int i=2;i<=n;i++)
    {
        cin>>p[i];
        adj[p[i]].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(adj[i].size()>1)
            is_linear=0;
    }
    ll a,b;
    dfs(1,1,1);
    while(q--)
    {
        cin>>a>>b;
        ll lc=lca(a,b);
        if(a==b)
        {
            cout<<"yes\n";
        }
        else
        {
            if(is_parent(b,a))
            {
                if(b==1)
                {
                    if(adj[a].size()>0)
                    {
                        cout<<"yes\n";
                    }
                    else
                    {
                        ll nod=nearest_sol2(a,lc);
                        //cout<<nod<<endl;
                        if(nod==MX)
                            cout<<"no\n";
                        else if(nod-lev[b]<lev[a]-nod)
                            cout<<"yes\n";
                        else
                            cout<<"no\n";
                    }
                }
                else
                {
                    cout<<"yes\n";
                }
            }
            else if(is_parent(a,b))
            {
                if(adj[b].size()>0)
                {
                    cout<<"yes\n";
                }
                else
                {
                    ll nod=nearest_sol(b,lc);
                    if(nod==0)
                        cout<<"no\n";
                    else if(lev[b]-nod<nod-lev[a])
                        cout<<"yes\n";
                    else
                        cout<<"no\n";

                }
            }
            else
            {
                ll lc=lca(a,b);
                if(dis(b,lc)<dis(a,lc))
                {
                    cout<<"yes\n";
                }
                else
                {
                    ll nod=nearest_sol(b,lc);
                    if(adj[b].size()>1)
                        cout<<"yes\n";
                    else if(nod==0)
                        cout<<"no\n";
                    else if(lev[b]-nod<lev[a]-lev[lc]+nod-lev[lc])
                        cout<<"yes\n";
                    else
                        cout<<"no\n";
                }
            }
        }

    }



    return 0;
}
Copy
Escape from TarkZoo Mr_Programmer_98
GNU G++17
61 ms
28.1 MB
Wrong Answer