CSP-S2019提高组day1-T2：括号树

题目链接

[CSP-S2019] 括号树

题目描述

本题中合法括号串的定义如下：

1. () 是合法括号串。
2. 如果 A 是合法括号串，则 (A) 是合法括号串。
3. 如果 A，B 是合法括号串，则 AB 是合法括号串。

本题中子串与不同的子串的定义如下：

1. 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S(l,r)$（$1\le l\le r\le |S|$，$|S|$ 表示 S 的长度）。
2. S 的两个子串视作不同当且仅当它们在 S 中的位置不同，即 $l$ 不同或 $r$ 不同。

一个大小为 $n$ 的树包含 $n$ 个结点和 $n?1$ 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。

小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 $n$ 的树，树上结点从 $1～n$ 编号，$1$ 号结点为树的根。除 $1$ 号结点外，每个结点有一个父亲结点，$u$（$2\le u\le n$）号结点的父亲为 $f_u$（$1\le f_u<u$）号结点。

小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。小 Q 定义 $s_i$ 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。

显然 $s_i$ 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 $i$（$1\le i\le n$）求出，$s_i$ 中有多少个互不相同的子串是合法括号串。

这个问题难倒了小 Q，他只好向你求助。设 $s_i$ 共有 $k_i$ 个不同子串是合法括号串， 你只需要告诉小 Q 所有 $i\times k_i$ 的异或和，即：
$$(1\times k_1)\text{xor}(2\times k_2)\text{xor}(3\times k_3)\text{xor}?\text{xor}(n\times k_n)$$
其中 $xor$ 是位异或运算。

输入格式

第一行一个整数 $n$，表示树的大小。

第二行一个长为 $n$ 的由( 与) 组成的括号串，第 $i$ 个括号表示 $i$ 号结点上的括号。

第三行包含 $n?1$ 个整数，第 $i$（$1\le i<n$）个整数表示 $i+1$ 号结点的父亲编号 $f_{i+1}$。

输出格式

仅一行一个整数表示答案。

样例 #1

样例输入 #1

5
(()()
1 1 2 2

样例输出 #1

6

提示

【样例解释1】

树的形态如下图：

将根到 1 号结点的简单路径上的括号，按经过顺序排列所组成的字符串为 (，子串是合法括号串的个数为 $0$。

将根到 2 号结点的字符串为 ((，子串是合法括号串的个数为 $0$。

将根到 3 号结点的字符串为 ()，子串是合法括号串的个数为 $1$。

将根到 4 号结点的字符串为 (((，子串是合法括号串的个数为 $0$。

将根到 5 号结点的字符串为 (()，子串是合法括号串的个数为 $1$。

【数据范围】

算法思想

根据题目描述，要求的是树中从根结点到 $i$ 号结点组成的括号串$s_i$中，合法括号串的个数。示例参考提示【样例解释1】。

对于任意括号串$s_i$如下图所示：

要计算括号串$s_i$中合法括号串的个数，不妨设为$f(i)$，从最后一步分析，也就是根据$i$号结点的选择分成两种情况：

• 不选择$i$号结点，那么方案数等于括号串$s_{i?1}$中合法括号串的个数，即$f(i?1)$
• 选择$i$号结点（前提是$i$号结点是)），那么以$i$结尾的合法括号串的个数如何计算呢，不妨设其为$g(i)$：
  • 首先找到与$i$号结点匹配的(的位置，不妨设为$j$（如上图所示），那么从$j$到$i$就是一组合法的括号串
  • 其次考虑$j$之前合法括号串的个数，即以$j?1$结尾的合法括号串的个数，就是$g[j?1]$，
  • 可得以$i$结尾的合法括号串的个数，就是在以$j?1$结尾的合法括号串后添加了$1$组，即$g[i]=g[j?1]+1$

那么，$f(i)=f(i?1)+g[i]$，其中$g[i]$表示以$i$结尾的合法括号串的个数，$g[i]=g[j?1]+1$，$j$是与$i$匹配的左括号(的位置。

进一步分析，以$j?1$结尾的合法括号串的个数$g[j?1]$，其实就是从根节点到$j?1$号结点的所有合法括号串中去掉不选择$j?1$号结点的方案数，即$g(j?1)=f(j?1)?f(j?2)$

综上所述，$f(i)=f(i?1)+f(j?1)?f(j?2)+1$，其中$j$是与$i$匹配的左括号(的位置。

通过上面的分析，要想进行计算还要解决两个问题：

• 在树上如何得到括号串$i$位置的上一个结点$i?1$？

在树上$i$位置的上一个结点，就是$i$的父节点，可以设置一个数组p[i]来存储i的父节点

• 如何得到与$i$匹配的左括号(的位置$j$？

括号匹配，可以通过栈来实现。如果i位置是左括号，直接入栈，如果i位置是右括号，则栈顶就是与之匹配的左括号的位置。

下面从动态规划的角度将上述分析整理一下。

状态表示

• $f[i]$表示树中从根结点到 $i$ 号结点组成的括号串$s_i$中合法括号串的个数

最终答案$=(1\times f[1])\text{xor}(2\times f[2])\text{xor}(3\times f[3])\text{xor}?\text{xor}(n\times f[n])$。注意$n$的范围很大（$n\le 5\times 10^5$），会爆int。

状态计算

从最后一步分析，根据$i$号结点的选择分成两种情况：

• 不选择$i$号结点，那么方案数等于括号串$s_{i?1}$中合法括号串的个数，即$f[p[i]]$，其中$p[i]$表示$i$的父结点，也就是括号串中$i$之前的结点
• 选择$i$号结点（前提是$i$号结点是)），先找到与$i$匹配的左括号的位置$j$，其父节点为$p[j]$，那么以以$i$结尾的合法括号串的个数为$f[p[j]]?f[p[p[j]]]+1$。

那么，$f[i]=f[p[i]]+f[p[j]]?f[p[p[j]]]+1$。

初始状态

根节点编号为$1$，根结点自己组成的合法括号串的个数为$0$，即$f[1]=0$。

时间复杂度

• 状态数为$n$
• 每个结点的状态只会计算一次，时间复杂度$O(1)$

总的时间复杂度为$O(n)$。

代码实现

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
char s[N];
int p[N], stk[N], top;
//f[i]表示树中从根结点到i号结点组成的括号串中合法的方案数
LL f[N]; 
vector<int> g[N]; //邻接表
void dfs(int i)
{
    if(s[i] == '(')
    {
        stk[++ top] = i; //左括号入栈
        f[i] = f[p[i]]; //不选择i号结点
        for(int k : g[i]) 
            dfs(k); //递归处理子结点
        top --; //回溯，恢复现场
    }
    else //右括号
    {
        if(top == 0) //栈空，没有与之匹配的左括号
        {
            f[i] = f[p[i]]; //不选择i号结点
            for(int k : g[i]) 
                dfs(k); //递归处理子结点
        }
        else
        {
            int j = stk[top --]; //从栈顶取出与i匹配的右括号位置
            f[i] = f[p[i]] + f[p[j]] - f[p[p[j]]] + 1; //状态计算
            for(int k : g[i]) 
                dfs(k); //递归处理子结点
            stk[++ top] = j; //回溯，恢复现场
        }
    }
}
int main()
{
    int n;
    scanf("%d%s", &n, s + 1);
    for(int i = 2; i <= n; i ++)
    {
        scanf("%d", &p[i]); //输入i的父结点
        g[p[i]].push_back(i); //将i添加到a的子结点中
    }
    
    dfs(1);
    
    LL ans = 0;
    for(int i = 1; i <= n; i ++) ans ^= i * f[i];
    printf("%lld\n", ans);
    return 0;
}