题面

不再多说，想必大家都看过这个题

思路

我们可以手推几个满足条件的字符串

我们发现在这些字符串里

每个）都与离它最近的（的匹配

所以我们维护树上每个节点到根节点中没用使用过的（的位置（nl[n]） h[i]表示以i的结尾的满足条件的串的个数

    nl[n] = nl[fa[n]];
    if(value[n] == 1)
    nl[n] = n;
    else
    {
        if(nl[n] != 0)
        {
        ll f = fa[nl[n]];
        nl[n] = nl[f];
    h[n] = 1 + h[f];//把离）最近的（使用
        }
    }

最后因为是字串 所以需要h[i]前缀和

（注意\(1<=f_u<u\)）

代码

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll M = 500015;
struct edge{
    ll to,next;
}QWQ[M];
ll head[M],n,fa[M],value[M],h[M],nl[M],ans;
void merge(ll x,ll y)
{
    QWQ[ ++QWQ[0].to ].to = x;
    QWQ[ QWQ[0].to ].next = head[y];
    head[y] = QWQ[0].to;
}
void dfs(ll n)
{
    nl[n] = nl[fa[n]];
    if(value[n] == 1)
    nl[n] = n;
    else
    {
        if(nl[n] != 0)
        {
        ll f = fa[nl[n]];
        nl[n] = nl[f];
        h[n] = 1 + h[f];
        }
    }
    for(ll i = head[n];i;i = QWQ[i].next)
    dfs(QWQ[i].to);
}
int main()
{
    scanf("%lld",&n);
    char c;
    for(ll i = 1;i <= n;i++)
    {
        c = getchar();
        while(c != '('&&c != ')')
        c = getchar();
        if(c == '(')
        value[i] = 1;
        if(c == ')')
        value[i] = 2;
    }
    for(ll i = 2;i <= n;i++)
    {
        scanf("%lld",&fa[i]);
        merge(i,fa[i]);
    }
    dfs(1);
    ans = h[1];
    for(ll i = 2;i <= n;i++)
    {
        ll j = i;
        h[i] += h[fa[j]];
        ans ^= i * h[i];
    }
    cout<<ans;
}