Source Code
#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>

#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define LL long long
#define LD long double
#define pb push_back
#define F first
#define S second


const double PI=3.1415926535897932384626433;
const int KL=2e5+10;
const LL MOD=1e9+7;


using namespace std;

const int lg=19;
int n,m,q,b,c,up[KL][lg],x,y,in[KL],out[KL],timer,dis[KL];
LL sum[KL][lg],a[KL];
vector <int> adj[KL];
void dfs(int node=1,int pr=1,int cnt=0){
    up[node][0]=pr;
    for(int j=1;j<lg;j++){
        up[node][j]=up[up[node][j-1]][j-1];
    }
    if(node!=1){
        sum[node][0]=a[pr];
        for(int j=1;j<lg;j++){
            sum[node][j]=sum[node][j-1]+sum[up[node][j-1]][j-1];
        }
    }
    in[node]=timer++;
    dis[node]=cnt;
    for(auto v:adj[node]){
        if(v==pr)continue;
        dfs(v,node,cnt+1);
    }
    out[node]=timer++;
}
bool isan(int node1,int node2){
    return (in[node1]<=in[node2] && in[node2]<=out[node1]);
}
int lca(int node1,int node2){
    if(isan(node1,node2))return node1;
    if(isan(node2,node1))return node2;
    for(int j=lg-1;j>=0;j--){
        if(!isan(up[node1][j],node2))node1=up[node1][j];
    }
    return up[node1][0];
}
int getkth(int node1,int k){
    for(int j=lg-1;j>=0;j--){
        if(k&(1<<j))node1=up[node1][j];
    }
    return node1;
}
LL getsum(int node1,int node2){
    if(node1==node2)return a[node1];
    int node3=lca(node1,node2);
    LL ret=a[node1]*(node1!=node3)+a[node2]*(node2!=node3);
    int k=dis[node1]-dis[node3];
    int node=node1,cnt=0;
    while(k!=0){
        if(k%2==1){
            ret+=sum[node][cnt];
            node=up[node][cnt];
        }
        cnt++;
        k/=2;
    }
    k=dis[node2]-dis[node3];
    node=node2,cnt=0;
    while(k!=0){
        if(k%2==1){
            ret+=sum[node][cnt];
            node=up[node][cnt];
        }
        cnt++;
        k/=2;
    }
    if(node1!=node3 && node2!=node3)ret-=a[node3];
    return ret;
}
bool ok(int k,int node){
    int fa=getkth(node,k);
    if(getsum(node,fa)-a[node]>k)return 1;
    return 0;
}
int main(){
    sc(n);sc(q);
    for(int i=2;i<=n;i++)sc(x),adj[x].pb(i);
    for(int i=1;i<=n;i++)a[i]=adj[i].size();
    for(int j=0;j<lg;j++)up[1][j]=1,sum[1][j]=0;
    dfs();
    while(q--){
        sc(x);sc(y);
        if(x==y){
            cout<<"yes"<<endl;
            continue;
        }
        int lst=0,z=lca(x,y),tot=dis[x]-dis[z]+dis[y]-dis[z];
        ///cout<<z<<" "<<tot<<endl;
        if(y==z){
            if(a[z]>1 || y!=1)lst=tot;
        }
        else {
            if(x!=z){
                if(a[z]>2 || z!=1)lst=max(lst,dis[x]-dis[z]);
            }
            if(a[y]>0)lst=max(lst,tot);
            int lo=1,hi=dis[y]-dis[z]-1;
            while(lo<hi){
                int mid=(lo+hi)/2;
                if(ok(mid,y))hi=mid;
                else lo=mid+1;
            }
            ///cout<<lo<<" "<<ok(lo,y)<<endl;
            if(ok(lo,y))lst=max(lst,dis[x]-dis[z]+(dis[y]-dis[z]-lo));
        }
        if(x!=z){
            int lo=1,hi=dis[x]-dis[z]-1;
            while(lo<hi){
                int mid=(lo+hi+1)/2;
                if(ok(mid,x))lo=mid;
                else hi=mid-1;
            }
            if(ok(lo,x))lst=max(lst,lo);
        }
        if(lst>tot-lst)cout<<"yes"<<endl;
        else cout<<"no"<<endl;


    }
}
Copy
Escape from TarkZoo Vectors_Master
GNU G++17
410 ms
38.1 MB
Accepted