记录编号	571561	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]括号树	最终得分	100
用户昵称	冷月星云	是否通过	通过
代码语言	C++	运行时间	0.278 s
提交时间	2022-05-29 08:57:29	内存使用	14.41 MiB

#include <bits/stdc++.h>
#define R register 
#define ull unsigned long long
#define ll long long

using namespace std;

int read(){
    R int x = 0, f = 1;
    R char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x*f;
}

ll n, head[500010], tot, dp[500010], lst[500010], gx[500010];
ll ans = 0;

struct node{
    int fa;
    char ch;
}p[500010];

struct edge{
    int to, next;
}e[500010];

void add(int u, int v)
{
    e[++tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

void update(int x)
{
    if(p[x].ch == '(')
        lst[x] = x, dp[x] = dp[p[x].fa], gx[x] = 0;
    else
    {
        if(lst[p[x].fa] > 0)
        {
            lst[x] = lst[p[lst[p[x].fa]].fa];
            gx[x] = gx[p[lst[p[x].fa]].fa] + 1;
            dp[x] = dp[p[x].fa] + gx[x];
        }
        else
        {
            lst[x] = 0;
            gx[x] = 0;
            dp[x] = dp[p[x].fa];
        }
    }
    return;
}

void dfs(int x)
{
    if(p[x].ch == '(')
        lst[x] = x, dp[x] = dp[p[x].fa], gx[x] = 0;
    else
    {
        if(lst[p[x].fa] > 0)
        {
            lst[x] = lst[p[lst[p[x].fa]].fa];
            gx[x] = gx[p[lst[p[x].fa]].fa] + 1;
            dp[x] = dp[p[x].fa] + gx[x];
        }
        else
        {
            lst[x] = 0;
            gx[x] = 0;
            dp[x] = dp[p[x].fa];
        }
    }
    for(R int i = head[x];i;i = e[i].next)
        dfs(e[i].to);
    return; 
}

int main()
{
    freopen("2019brackets.in","r",stdin);
	freopen("2019brackets.out","w",stdout);
    n = read();
    for(R int i = 1; i <= n; ++i)
        scanf("%c",&p[i].ch);
    for(R int i = 2; i <= n; ++i)
        p[i].fa = read(), add(p[i].fa, i);
    dfs(1);
    for(R ll i = 1; i <= n; ++i)
        ans = ans xor (i*dp[i]);
    cout << ans;
    return 0;
}