Submission #2968462

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int n,k,q,sz[100005],hv[100005],vs[100005],hd[100005],dp[100005],cn[100005],id[1000005],bit[100005],pa[100005],c[100005];
vector<int>g[100005];
void dfs(int v,int p){
    sz[v]=1;
    hv[v]=-1;
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p){
            dfs(g[v][i],v);
            sz[v]+=sz[g[v][i]];
            if(hv[v]==-1||sz[hv[v]]<sz[g[v][i]])hv[v]=g[v][i];
        }
    }
}
void dfs1(int v,int d,int p,int h){
    hd[k]=h;
    cn[k]=cn[h];
    id[v]=k;
    vs[k]=v;
    dp[k++]=d;
    if(hv[v]!=-1)dfs1(hv[v],d+1,v,h);
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p&&g[v][i]!=hv[v]){
            cn[k]=id[v];
            dfs1(g[v][i],d+1,v,k);
        }
    }
}
void add(int a,int b){
    a++;
    while(a<=n){
        bit[a]+=b;
        a+=(a&-a);
    }
}
int su(int a){
    a++;
    int res=0;
    while(a>0){
        res+=bit[a];
        a-=(a&-a);
    }
    return res;
}
int sum(int a,int b){
    return su(b)-su(a-1);
}
int lca(int u,int v){
    int res=0;
    u=id[u];v=id[v];
    while(hd[u]!=hd[v]){
        if(dp[hd[u]]>dp[hd[v]]){
            res+=sum(hd[u],u);
            u=cn[u];
        }else{
            res+=sum(hd[v],v);
            v=cn[v];
        }
    }
    return res+sum(min(u,v)+1,max(u,v));
}
int main(void){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>pa[i];
        g[--pa[i]].push_back(i);
    }
    dfs(0,-1);
    dfs1(0,0,-1,0);
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    for(int i=1;i<n;i++){
        if(c[i]==c[pa[i]]){
            pa[i]=1;
            add(id[i],1);
        }else pa[i]=0;
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int t;
        cin>>t;
        if(t==1){
            int v;
            cin>>v;
            v--;
            if(v==0)continue;
            if(pa[v]==1){
                add(id[v],-1);
                pa[v]=0;
            }else{
                add(id[v],1);
                pa[v]=1;
            }
        }else{
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            if(lca(u,v)==0)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}

Submission Info

Judge Result