「CSP2019 T」括号树
背景
- Idea: CCF
- Data: CCF
- Solution: CCF
- 题面: CCF + oistream
本题中 合法括号串 的定义如下:
()
是合法括号串。- 如果
A
是合法括号串,则(A)
是合法括号串。 - 如果
A
,B
是合法括号串,则AB
是合法括号串。
本题中 子串 与 不同的子串 的定义如下:
- 字符串 \(S\) 的子串是 \(S\) 中 连续 的任意个字符组成的字符串。\(S\) 的子串可用起始位置 \(l\) 与终止位置 \(r\) 来表示,记为 \(S(l,r)\)(\(1\leq l\leq r\leq |S|\),\(|S|\) 表示 \(S\) 的长度)
- \(S\) 的两个子串视作不同 当且仅当 它们在 \(S\) 中的位置不同,即 \(l\) 不同或 \(r\) 不同。
描述
一个大小为 \(n\) 的树包含 \(n\) 个结点和 \(n-1\) 条边,每条边连接两个结点,且任意两个结点间 有且仅有 一条简单路径互相可达。
小 Q 是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为 \(n\) 的树,树上结点从 \(1\sim n\) 编号,\(1\) 号结点为树的根。除 \(1\) 号结点外,每个结点有一个父亲结点,\(u~~(2\leq u\leq n)\) 号结点的父亲为 \(f_u~~(1\leq f_u\lt u)\) 号结点。
小 Q 发现这个树的每个结点上 恰有 一个括号,可能是(
或)
。小 Q 定义 \(s_i\) 为:将根结点到 \(i\) 号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。
显然 \(s_i\) 是个括号串,但不一定是合法括号串,因此现在小 Q 想对所有的 \(i~~(1\leq i\leq n)\)求出,\(s_i\) 中有多少个 互不相同的子串 是 合法括号串 。
这个问题难倒了小 Q,他只好向你求助。设 \(s_i\) 共有 \(k_i\) 个不同子串是合法括号串, 你只需要告诉小 Q 所有 \(i\times k_i\) 的异或和,即:
\[(1\times k_1)\oplus (2\times k_2)\oplus (3\times k_3)\oplus \cdots \oplus (n\times k_n)\]
其中 \(\oplus\) 是位异或运算。
输入格式
第一行一个整数 \(n\),表示树的大小。
第二行一个长为 \(n\) 的由(
与)
组成的括号串,第 \(i\) 个括号表示 \(i\) 号结点上的括号。
第三行包含 \(n-1\) 个整数,第 \(i~~(1\leq i\lt n)\) 个整数表示 \(i+1\) 号结点的父亲编号 \(f_{i+1}\) 。
输出格式
仅一行一个整数表示答案。
样例
输入样例1
5
(()()
1 1 2 2
输出样例1
6
样例解释
样例解释1
树的形态如下图。
将根到 \(1\) 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 (
,子串是合法括号串的个数为 \(0\)。
根到 \(2\) 号结点的字符串为 ((
,子串是合法括号串的个数为 \(0\)。
根到 \(3\) 号结点的字符串为 ()
,子串是合法括号串的个数为 \(1\)。
根到 \(4\) 号结点的字符串为 (((
,子串是合法括号串的个数为 \(0\)。
根到 \(5\) 号结点的字符串为 (()
,子串是合法括号串的个数为 \(1\)。
数据规模与约定
如下表所示( 若不填则代表同上一格 )
测试点编号 | \(n\leq \) | 特殊性质 |
---|---|---|
\(1\sim 2\) | \(8\) | \(f_i=i-1\) |
\(3\sim 4\) | \(200\) | |
\(5\sim 7\) | \(2000\) | |
\(8\sim 10\) | 无 | |
\(11\sim 14\) | \(10^5\) | \(f_i=i-1\) |
\(15\sim 16\) | \(10^5\) | 无 |
\(17\sim 20\) | \(5\times 10^5\) |
信息
- ID
- 1126
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 被复制
- 1
- 上传者
相关
在下列训练计划中: