【CSP2019】括号树 | Mrsrz's blog

栈，DP

题目大意：

给定一棵树，每个结点为左括号或者右括号。

一个结点代表的串为从根到该结点的所有括号依次排列形成。

对每个结点，求其代表的串中，有多少子串的括号完全匹配。

题解：

考虑令 $f_i$ 表示以 $i$ 结尾的合法子串的个数。显然 $f_i\neq 0$ 必须满足 $i$ 位置是右括号。

由于以 $i$ 结尾的串唯一确定，可以找到一个唯一确定的位置 $x$ 满足 $x$ 左括号，且 $x$ 和 $i$ 中间的串是完全匹配的。

那么从 $x$ 到 $i$ 的这段是完全匹配的，并且是以 $i$ 结尾的完全匹配的串中最短的。

其他以 $i$ 结尾的匹配的串，必定是之前的一段匹配的串，和 $x$ 到 $i$ 这段拼接而成的。这些串的个数为 $f_{fa[x]}$。

那么显然的转移为 $f_i=f_{fa[x]}+1$。

我们只要知道一个点对应的 $x$ 就好了。

这个很容易用栈维护。在遍历树的时候，左括号扔栈里，遇到右括号，则栈顶的左括号就是它所对应的 $x$，然后把这个括号弹出即可。

遍历时需要涉及回滚操作。由于每个结点对栈的修改是 $O(1)$ 的，所以记录一下这层干了什么，就可以方便地回滚。

最后对 $f$ 做一遍到根路径的前缀和即可。

时间复杂度 $O(n)$。

注意没得匹配的右括号的情况。

Code：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N=5e5+6;
int n,head[N],cnt,fa[N];
LL f[N];
char s[N];
struct edge{
    int to,nxt;
}e[N];
int sta[N],top=0;
void dfs(int now){
    int bak=0;
    if(s[now]=='(')sta[++top]=now;else
    if(top&&s[sta[top]]=='('){
        bak=sta[top];
        f[now]=1+f[fa[bak]];
        --top;
    }else sta[++top]=now;
    for(int i=head[now];i;i=e[i].nxt)
    dfs(e[i].to);
    if(bak)sta[++top]=bak;else --top;
}
void dfs2(int now){
    for(int i=head[now];i;i=e[i].nxt)f[e[i].to]+=f[now],dfs2(e[i].to);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>(s+1);
    for(int i=2;i<=n;++i){
        cin>>fa[i];
        e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
    }
    dfs(1);dfs2(1);
    LL ans=0;
    for(int i=1;i<=n;++i)
    ans^=i*f[i];
    cout<<ans<<'\n';
    return 0;
}