hddg

铁盒 · 2019-11-23 11:37:20 · 个人记录

#include<iostream>
using namespace std;
long long n,s[1000000],f[1000000],father[1000000],h[1000000],ans;
char c[1000000];
int main(){
    scanf("%I64d",&n);
    cin>>c+1;
    for (long long i=2;i<=n;i++){
      scanf("%I64d",&father[i]);
    } 
    for (long long i=2;i<=n;i++){
        if (c[i]=='('){
            s[i]=0;
            h[i]=0;
        } 
        else
        {
            if (c[father[i]]==')'){
                if ((c[father[h[father[i]]]]=='(')){
                    h[i]=father[h[father[i]]];
                    s[i]=s[father[h[i]]]+1;
                    if (h[father[h[i]]]!=0){
                        h[i]=h[father[h[i]]];
                    }
                }
            }
            else{
                h[i]=f[i];
                s[i]=s[father[h[i]]]+1;
                if(h[father[h[i]]]!=0)
                    h[i]=h[father[h[i]]];
            }
        }
        f[i]=f[father[i]]+s[i];
    }
    ans=0;
    for (int i=1;i<=n;i++)
        ans=ans^(i*f[i]);
    printf("%I64d",ans);
    return 0;
}