Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ss second
#define ff first
#define pb push_back
#define mp make_pair
ll n,m;
vector<int> v[200100];
ll dp[21][200100];
bool ok[21][200100],ok2[200100];
int dis[200100];
void go(int cr,int p,int y){
    dp[0][cr]=p;
    dis[cr]=y;
    if(v[cr].size()>=3)ok2[cr]=1;
    if(v[p].size()>=3)ok[0][cr]=1;
    for(int i=0;i<v[cr].size();i++){
        if(v[cr][i]==p)continue;
        go(v[cr][i],cr,y+1);
    }
}
int lca(int l,int r){
    if(dis[l]<dis[r])swap(l,r);
    for(int i=20;i>=0;i--){
        if(dis[l]-(1<<i)>dis[r]){
            l=dp[i][l];
        }
    }

    //l=dp[0][l];
    if(dp[0][l]==r)return r;
    if(dis[l]>dis[r])
    l=dp[0][l];
    for(int i=20;i>=0;i--){
        if(dp[i][l]!=dp[i][r]){
            l=dp[i][l];
            r=dp[i][r];
           // cout<<i<<endl;
        }
    }
     //cout<<l<<' '<<r<<endl;
    return dp[0][l];
}
bool lck(int cr,int r){
    bool k=0;
    for(int i=20;i>=0;i--){
        if((1<<i)<=r){
            r-=(1<<i);
            k=max(k,ok[i][cr]);
            cr=dp[i][cr];
        }
    }
    return k;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int a;
        cin>>a;
        v[i].pb(a);
        v[a].pb(i);
    }
    go(1,0,1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            dp[j][i]=dp[j-1][dp[j-1][i]];
            ok[j][i]=max(ok[j][i],max(ok[j-1][ok[j-1][i]],ok2[dp[j-1][i]]));
        }
    }

    while(m--){
        int l,r;
        cin>>l>>r; int h=lca(l,r); //cout<<h<<endl;
        if(v[r].size()>=2||l==r){
            cout<<"yes\n";
            continue;
        }

        int rod=dis[l]-dis[h]+dis[r]-dis[h];
        int y=dis[l]-dis[h];
        int hi=y,lo=1,best=0;

        while(hi>=lo){
            int mid=(hi+lo)/2;
            bool k=lck(l,mid);
            if(k){
                best=max(best,mid);
                lo=mid+1;
            }
            else hi=mid-1;
        }  //cout<<ok[1][l]<<' '<<dp[1][l];
        if(rod-best<best){
             cout<<"yes\n";
            continue;
        }
        y=dis[r]-dis[h];
        hi=y;lo=1;best=1e8;
        while(hi>=lo){
            int mid=(hi+lo)/2;
            bool k=lck(r,mid);
            if(k){
                best=min(best,mid);
                hi=mid-1;
            }
            else lo=mid+1;
        }

        if(best<(rod+1)/2){
             cout<<"yes\n";
            continue;
        }
        cout<<"no\n";

    }

}
/*
5 3
1 3 3 2 4 6
-1 -5 -10 4 -3 5
1 3 2

*/
Copy
Escape from TarkZoo Wesam
GNU G++17
36 ms
15.1 MB
Wrong Answer