题目：括号树（DP）

题目

思路

定义\(dp_i\)为从i号节点从上的()()()()····的长度
之后在定义\(sum_i\)为从根结点到i的节点的单个括号的数量
有了这两个定义之后
用一个stack来维护就行了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
struct node
{
    int u;
    char c;
};
long long ans;
long long n;
long long summ[500005];
long long dp[500005];
int lena;
int faa[500005];
bool vis[500005];
char a[500005];
vector<int> g[500005];
stack<node> s;
void dfs(int u,int fa)
{
    faa[u]=fa;
    bool f=0;
    node t;
    if(!s.empty())
    {
        if(a[u]==')'&&s.top().c=='(')
        {
            f=1;
            t=s.top();
            if(a[fa]=='(')
            {
                summ[u]=summ[fa]+1;
                dp[u]=dp[faa[fa]]+1;
                summ[u]+=dp[faa[fa]];
            }
            else
            {
                summ[u]=summ[fa]+1;
                dp[u]=dp[faa[s.top().u]]+1;
                summ[u]+=dp[faa[s.top().u]];
            }
            s.pop();
        }
        else
        {
            summ[u]=summ[fa];
            node t1;
            t1.u=u;
            t1.c=a[u];
            s.push(t1);
        }
    }
    else
    {
        summ[u]=summ[fa];
        node t1;
        t1.u=u;
        t1.c=a[u];
        s.push(t1);
    }
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v!=fa)
        {
            dfs(v,u);
        }
    }
    if(f)
    {
        s.push(t);
    }
    else
    {
        s.pop();
    }
    ans^=(1ll*u*summ[u]);
}
int main()
{
    freopen("brackets.in","r",stdin);
    freopen("brackets.out","w",stdout);
    scanf("%lld",&n);
    scanf("%s",a);
    lena=strlen(a);
    for(int i=lena;i>=1;i--)
        a[i]=a[i-1];
    for(int i=2,u;i<=n;i++)
    {
        scanf("%d",&u);
        g[u].push_back(i);
    }
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}