2013年11月9日 星期六

[ZJ] a651: D. 小可魚兒向上游


#include<stdio.h>
#include<string.h>
int p[100005],v[100005],s[100005],root[100005];
int find(int k){
    return v[k] ? k : p[k]=find(p[k]);
}
int main(){
    int t,n,m,i,j,x,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(v,0,sizeof(v));
        memset(root,-1,sizeof(root));
        p[0]=0,v[0]=1;
        for(i=1;i<n;i++){
            scanf("%d",&x);
            p[i]=x;
        }
        for(i=0;i<m;i++)
            scanf("%d",&s[i]),v[s[i]]=1;
        for(i=m-1;i>=0;i--){
            if(s[i]) v[s[i]]=0;
            root[i]=find(s[i]);
        }
        ans=root[0]+1;
        for(i=1;i<m;i++)
            ans^=root[i]+i+1;
        printf("%d\n",ans);
    }
}

沒有留言:

張貼留言