[CSP-S 2019] 括号树

GitHub跳转原题关系图返回列表

按 f_u<u 的编号顺序递推，用父结点继承的未匹配左括号栈，求以每个结点结尾的合法括号子串数。

OJ: luogu

题目 ID: P5658

难度:提高+/省选-

标签:树形结构栈动态规划

创建: 2026-07-06 08:28

更新: 2026-10-07 10:45

前置题目

luogu P1722矩阵 IIB 的两条解法线都站在 A 教的「任意前缀不失衡即合法括号串」这一步上：brute.cpp 的 is_valid 直接照该判据扫描（balance<0 即非法），main.cpp 则把同一条前缀差非负判据实现成未匹配左括号栈（stack_top[fa]!=0 才配对），再叠加 A 未教的树上 total_count[u]=total_count[f_u]+end_count[u] 拆解、end_count[u]=end_count[f_p]+1 配对观察与 stack_next 共享栈。

形式化题目

给定一棵以结点 $1$ 为根的树，共 $n$ 个结点，父亲满足 $f_u<u$ 。每个结点 $u$ 上有一个括号 $c_u\in\{\texttt{(},\texttt{)}\}$ 。

记 $s_u$ 为根到 $u$ 的简单路径上的括号按经过顺序拼接得到的字符串。设 $k_u$ 为 $s_u$ 中位置不同的合法括号子串个数，求

(1k_1)\oplus(2k_2)\oplus\cdots\oplus(nk_n).

其中 $\oplus$ 是位异或。所谓“位置不同”，是指子串的起止位置 $(l,r)$ 不同，即使内容相同也分别计数。

样例 $1$ 的树如下，结点上标注了它对应的括号。

flowchart TD
  N1["1: ("] --> N2["2: ("]
  N1 --> N3["3: )"]
  N2 --> N4["4: ("]
  N2 --> N5["5: )"]

从图中可以看到根到每个结点的路径： $s_1=\texttt{(}$ ， $s_2=\texttt{((}$ ， $s_3=\texttt{()}$ ， $s_4=\texttt{(((}$ ， $s_5=\texttt{(()}$ 。只有 $s_3$ 与 $s_5$ 各含一个合法子串，所以答案是 $3\oplus 5=6$ 。

暴力解法

思路

最直接的做法是照着题意把每个 $s_u$ 都构造出来，再枚举它的所有子串，逐个判断是不是合法括号串。

判断合法性用括号匹配的经典判据：从左到右扫描，任意前缀的 ( 数都不少于 ) 数，且最后两者数量相等。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 20:19
 * update_at: 2026-10-01 20:39
 */
// brute.cpp：小数据暴力解，逐个构造根到结点的括号串，再枚举所有子串检查是否合法。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;   // 暴力只用于小数据对拍，n 取到 100 左右

int n;
char bracket_char[MAXN];   // bracket_char[u]：结点 u 上的括号
int parent_node[MAXN];     // parent_node[u]：u 的父亲，根结点 1 的父亲记为 0

// 判断 s[l..r] 是否为合法括号串：任意前缀和非负，且最终总和为 0。
bool is_valid(const string &s, ll l, ll r) {
    ll balance = 0;
    for (ll i = l; i <= r; i++) {
        if (s[i] == '(') {
            balance++;
        } else {
            balance--;
        }
        if (balance < 0) {
            return false;
        }
    }
    return balance == 0;
}

// 拼出根到结点 u 的括号串：先按 u 到根的顺序取字符，再整体反转。
string build_path_string(int u) {
    string path_string;
    while (u != 0) {
        path_string.push_back(bracket_char[u]);
        u = parent_node[u];
    }
    reverse(path_string.begin(), path_string.end());
    return path_string;
}

// 枚举 s 的所有子串，统计其中合法括号串的个数。
ll count_valid_substrings(const string &s) {
    ll len = s.size();
    ll count_answer = 0;
    for (ll l = 0; l < len; l++) {
        for (ll r = l; r < len; r++) {
            if (is_valid(s, l, r)) {
                count_answer++;
            }
        }
    }
    return count_answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> (bracket_char + 1);   // 直接读到下标 1 开始，和结点编号对齐
    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i];
    }

    ll answer = 0;
    for (int u = 1; u <= n; u++) {
        string path_string = build_path_string(u);
        ll k_u = count_valid_substrings(path_string);
        answer ^= u * k_u;
    }

    cout << answer << '\n';
    return 0;
}

复杂度

每个结点要拼一次路径，再枚举 $O(n^2)$ 个子串、每个子串 $O(n)$ 判定，单结点是 $O(n^3)$ ，全部结点 $O(n^4)$ ，空间 $O(n)$ 。

瓶颈

这个做法把“不同子串按位置计数”完整做了一遍，思路最贴近题意，但连 $n=2000$ 都跑不动。瓶颈有两处：

每个结点都重新拼一遍路径；
每个结点都重新枚举一遍子串。

题目要求 $n\leqslant 5\times10^5$ ，这两处都必须消掉。

正解

思路

把问题拆成“旧的 + 新增的”

从父亲 $f_u$ 走到 $u$ 时，路径字符串只在末尾多了一个字符。因此 $s_u$ 的合法括号子串要么原来就在 $s_{f_u}$ 里，要么必须以 $u$ 结尾。设

$end\_count[u]$ ： $s_u$ 中以结点 $u$ 结尾的合法括号子串数量；
$total\_count[u]$ ： $s_u$ 中全部合法括号子串数量，即题面的 $k_u$ 。

于是

total\_count[u]=total\_count[f_u]+end\_count[u].

第一处瓶颈就此消除：父亲的答案可以直接复用，不必重新枚举。

关键观察：与右括号配对的左括号是唯一确定的

如果 $c_u=\texttt{(}$ ，任何合法括号串都不可能以它结尾，直接有 $end\_count[u]=0$ 。

如果 $c_u=\texttt{)}$ ，设 $p$ 是根到 $u$ 的路径上、 $u$ 左边最近的未被匹配左括号，也就是对前缀 $s_u$ 做括号匹配时与 $u$ 配对的左括号。

任意一个以 $u$ 结尾的合法括号子串 $T$ ，都对应路径上一段连续区间 $[l,u]$ 。 $T$ 本身是合法括号串，而合法括号串内部的配对关系与在整个前缀 $s_u$ 中的配对关系一致，所以 $T$ 里与末尾那个 ) 配对的左括号必然就是 $p$ 。

于是 $T=[l,p]\cup[p+1,u]$ 。其中 $[p+1,u]$ 已经是一对合法括号，剩下的 $[l,p-1]$ 也必须是一个以 $f_p$ 结尾的合法括号串（或者为空）。以 $f_p$ 结尾的合法括号串有 $end\_count[f_p]$ 个，再加上“ $[l,p-1]$ 为空、 $T$ 就是 $[p,u]$ ”这一种，得到

end\_count[u]=end\_count[f_p]+1.

这里必须用 $end\_count[f_p]$ 而不是 $total\_count[f_p]$ ：能和 $[p,u]$ 拼在一起的合法串必须紧贴在 $p$ 前面，因此必须以 $f_p$ 结尾； $total\_count[f_p]$ 里那些更早结束的串中间隔着字符，拼不成连续子串。

让每个结点都有一份栈

现在只剩第二处瓶颈：如何快速找到 $p$ ，而且不重复扫描路径前缀。

沿一条路径走时，未匹配左括号天然构成一个栈：遇到 ( 压入，遇到 ) 弹出栈顶。链上的情况可以维护一个全局栈，但树会分叉，回溯时恢复现场很麻烦。更干净的做法是让每个结点只记录栈顶，栈本身通过父亲方向共享：

stack_top[u]：处理完结点 $u$ 之后，根到 $u$ 路径上的未匹配左括号栈顶结点编号（ $0$ 表示栈空）；
stack_next[x]：结点 $x$ 在栈中的下一个结点，沿着它就能还原整条栈。

转移就很直接：

$c_u=\texttt{(}$ ： $u$ 自己成为新栈顶，stack_top[u] = u，并令 stack_next[u] = stack_top[f_u]；
$c_u=\texttt{)}$ 且 stack_top[f_u] != 0：栈顶 $p$ 被匹配弹出，stack_top[u] = stack_next[p]，同时取 $end\_count[u]=end\_count[f_p]+1$ ；
$c_u=\texttt{)}$ 且栈空：stack_top[u] = 0， $end\_count[u]=0$ 。

每个结点只会写入一次 stack_next[u]（只有在它自己是 ( 时才写），而不同分支的结点各自持有自己的指针，因此共享前缀不会互相干扰，栈的总空间是 $O(n)$ 。

题目保证 $f_u<u$ ，所以按 $u=1,2,\ldots,n$ 的顺序递推时父亲一定已经算完，连 DFS 都不需要。

样例推演

下表用样例 $1$ 走一遍。约定 $f_1=0$ ，且 $end\_count[0]=total\_count[0]=0$ 。

结点 $u$	$c_u$	匹配到的 $p$	`stack_top[u]`	$end\_count[u]$	$total\_count[u]$
$1$	`(`	无	$1$	$0$	$0$
$2$	`(`	无	$2$	$0$	$0$
$3$	`)`	$1$	$0$	$end\_count[f_1]+1=1$	$total\_count[1]+1=1$
$4$	`(`	无	$4$	$0$	$0$
$5$	`)`	$2$	$1$	$end\_count[f_2]+1=1$	$total\_count[2]+1=1$

最后 $(1\cdot0)\oplus(2\cdot0)\oplus(3\cdot1)\oplus(4\cdot0)\oplus(5\cdot1)=3\oplus5=6$ ，与样例一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 20:19
 * update_at: 2026-10-01 20:39
 */
// main.cpp：题目保证 f_u < u，按结点编号从小到大递推，用两个数组模拟“根到当前结点的未匹配左括号栈”。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;   // n <= 5e5，结点编号用 int 足够，还能直接当数组下标

int n;
char bracket_char[MAXN];   // bracket_char[u]：结点 u 上的括号
int parent_node[MAXN];     // parent_node[u]：u 的父亲，根结点 1 的父亲记为 0

// 用两个数组表示根到 u 路径上“尚未匹配的左括号”栈：
// stack_top[u] 是 u 处栈顶结点的编号（0 表示栈空），
// stack_next[x] 是结点 x 在栈中的下一个结点，沿着它就能还原整条栈。
// 这样每个结点只需从父亲处继承栈顶，不必在回溯时恢复现场。
int stack_top[MAXN];
int stack_next[MAXN];

ll end_count[MAXN];    // end_count[u]：根到 u 的串中，以结点 u 结尾的合法括号子串数
ll total_count[MAXN];  // total_count[u]：根到 u 的串中全部合法括号子串数，即题面的 k_u

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> (bracket_char + 1);   // 直接读到下标 1 开始，和结点编号对齐
    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i];
    }

    ll answer = 0;

    // f_u < u 保证按编号递增递推时，父亲一定已经算完，因此不需要 DFS。
    for (int u = 1; u <= n; u++) {
        int fa = parent_node[u];

        if (bracket_char[u] == '(') {
            // 左括号自己入栈，成为新的栈顶，没有合法括号串以它结尾。
            end_count[u] = 0;
            stack_next[u] = stack_top[fa];
            stack_top[u] = u;
        } else if (stack_top[fa] != 0) {
            // 右括号与父亲路径上最近的未匹配左括号 left_node 配对，
            // 再接到以 left_node 父亲结尾的合法串后面。
            int left_node = stack_top[fa];
            end_count[u] = end_count[parent_node[left_node]] + 1;
            stack_top[u] = stack_next[left_node];
        } else {
            // 栈空，说明当前右括号配不到左括号，不能作为任何合法子串的结尾。
            end_count[u] = 0;
            stack_top[u] = 0;
        }

        total_count[u] = total_count[fa] + end_count[u];
        answer ^= u * total_count[u];
    }

    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$ 。每个结点只处理一次，压栈、弹栈、递推都是 $O(1)$ 。
空间复杂度： $O(n)$ 。需要存父亲、括号、两个栈数组和两个计数数组，均为 $n$ 级别。

总结

这题的核心是不要把路径上的子串真的枚举出来，而是拆成

total\_count[u]=total\_count[f_u]+end\_count[u].

当 $c_u=\texttt{)}$ 且匹配到左括号 $p$ 时，

end\_count[u]=end\_count[f_p]+1.

这个式子只看“紧贴在 $p$ 前面、并且以 $f_p$ 结尾”的合法串，因此用的是 $end\_count$ 而不是 $total\_count$ 。

实现上，用 stack_top 记录每个结点的栈顶、用 stack_next 共享栈结构，就不必在回溯时恢复现场，一次线性递推即可处理任意分叉的树。

本文的 main.cpp 已用逐路径枚举子串的 brute.cpp 对拍 $400$ 组随机数据（链与随机树各半）。

P5658 [CSP-S 2019] 括号树

题目背景

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

() 是合法括号串。
如果 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 ≤ f_u < 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)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)

其中

\text{xor}

是位异或运算。

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

text

1
2
35
(()()
1 1 2 2

输出 #1

text

说明/提示

【样例 1 解释】

树的形态如下图：

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

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

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

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

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

【样例 2】

见选手目录下的 brackets/brackets2.in 与 brackets/brackets2.ans。

【数据范围】

::cute-table{tuack}

测试点编号	$n\le$	特殊性质
$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$	^	无
$17\sim 20$	$5\times 10^5$	^