洛谷P5658 [CSP-S2019] 括号树 题解

题目链接：P5658 [CSP-S2019] 括号树

题意：略。

注意到本题中，链的部分分很高，就先考虑这种情况

不难发现，每个与 $l$ 配对的右括号 $r$ 的贡献为 $dp[r]=dp[l-1]+1 = dp[fa[l]]+1$

则 $k_i = dp[i] + \sum dp[j]$ ，$j$ 是 $i$ 的祖先结点

显然这个性质可以推广到树上

这样维护一个括号栈就好了，怎么维护呢？

为了防止栈在回溯过程中被破坏，考虑回溯时执行相反操作

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)

int n,fa[N],sum[N];
char val[N];
struct Edge
{
    int u,v,next;
}e[N];
int pos=1,head[N],dp[N],stk[N],top;
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u)
{
    int t=0;
    if(val[u]==')')
    {
        if(top)
        {
            t=stk[top--];
            dp[u]=dp[fa[t]]+1;
        }
    }else stk[++top]=u;
    sum[u]=sum[fa[u]]+dp[u];
    for(int i=head[u]; i; i=e[i].next)
        dfs(e[i].v);
    if(t)stk[++top]=t;
    else if(top)--top;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (val+1);
    for(int i=2; i<=n; i++)
    {
        cin >> fa[i];
        addEdge(fa[i],i);
    }
    dfs(1);int res=0;
    for(int i=1; i<=n; i++)
        res^=i*sum[i];
    cout << res;
    return 0;
}