CSP-S 2019 D1T2 括号树

题目链接：[https://www.luogu.com.cn/problem/P5658]

思路：

这道题不难。（为什么我在考场上一点思路也没有？？）
假设我们已经处理到树上的节点u（假设1为根节点），那么可以知道：

\([1,u]的合法括号串数=[1,fa[u]]的合法括号串数+u处新增的合法括号串数\)

对于前者，直接继承即可。
对于后者，我们令f[u]表示u节点新增的合法括号串数，栈s表示还未被匹配的‘(’所处在的节点，那么可以得到：

• u的字符为‘(’：\(s[++top]=u，f[u]=0\)
• u的字符为‘)’：
  ---- 1. \(top==0\)（即栈为空）\(f[u]=0\)
  ---- 2. \(top>0\) （即栈非空）\(f[u]=f[fa[s[top]]]+1,top--\)
  (意思是u处新得到的合法括号串数要么由\([1,fa[s[top]]\)（即栈顶父亲）\(]\)的合法括号串数加这对括号得到，要么由\(s[top]\)与\(u\)这对括号本身匹配得到)

具体实现：

用数组模拟栈即可。需要注意的是当搜索完部分子树后，栈s中某些元素可能会被覆盖，在这种情况下就需要回溯时在加回去（具体见代码）

注意事项：

做本题时态拘泥于以前的想法与思路，没有跳出来对本题进行分析。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,tot;
ll ans,f[N];
int fi[N],ne[N],to[N],s[N],fa[N];
char ch[N];
inline int read()
{
    int s=0,w=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return s*w; 
}
inline void add(int x,int y)
{
    ne[++tot]=fi[x],fi[x]=tot,to[tot]=y;
}
void dfs(int u,ll pre,int tp)
{
    int pd=0;//pd即用来处理特殊情况的
    if(ch[u]=='(') s[++tp]=u;
    else
    {
        if(!tp) f[u]=0;
        else
        {
            pd=s[tp];//要出栈了，记下此时的栈顶
            f[u]=f[fa[s[tp]]]+1;
            pre+=f[u];
            tp--;
        }
    }
    ans^=(u*pre);
    for(int i=fi[u],v=to[i];i;v=to[i=ne[i]])
        dfs(v,pre,tp);
    if(pd) s[tp+1]=pd;//回溯时再加回来
}
int main()
{
    n=read();
    scanf("%s",ch+1);
    for(int i=2;i<=n;++i)add(fa[i]=read(),i);
    dfs(1,0,0);
    printf("%lld\n",ans);
    return 0;
}

CSP-S 2019 D1T2 括号树

原文：https://www.cnblogs.com/zmyzmy/p/11924878.html