[CSP-S 2019] 括号树

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

DFS 维护根到当前节点路径上的未匹配左括号栈，统计每个节点新增的以当前点结尾的合法括号子串数。

OJ: luogu

题目 ID: P5658

难度:提高+/省选-

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

日期: 2026-07-06 08:28

题意

有一棵以 1 为根的树，每个节点上有一个括号，可能是 (，也可能是 )。

对每个节点 i，把根到 i 的路径上的括号按顺序拼起来，得到字符串 s_i。

设 k_i 表示 s_i 中有多少个不同位置的子串是合法括号串。题目要求输出：

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

这里的“不同子串”按位置区分。也就是说，即使两个子串内容都等于 ()，只要起止位置不同，也算两个不同子串。

思路

先看一个最直接的暴力做法：

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// brute.cpp：小数据暴力解，逐个构造根到节点的括号串，再枚举所有子串检查是否合法。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
string bracket_string;
int parent_node[MAXN];

bool is_valid(const string &s, int l, int r) {
    int balance = 0;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(') {
            balance++;
        } else {
            balance--;
        }
        if (balance < 0) {
            return false;
        }
    }
    return balance == 0;
}

string build_path_string(int u) {
    vector<int> nodes;
    while (u != 0) {
        nodes.push_back(u);
        u = parent_node[u];
    }
    reverse(nodes.begin(), nodes.end());

    string s;
    for (int i = 0; i < (int)nodes.size(); i++) {
        s.push_back(bracket_string[nodes[i] - 1]);
    }
    return s;
}

long long count_valid_substrings(const string &s) {
    long long count_answer = 0;
    int len = (int)s.size();
    for (int l = 0; l < len; l++) {
        for (int 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_string;
    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i];
    }

    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        string path_string = build_path_string(i);
        long long k_i = count_valid_substrings(path_string);
        answer ^= 1LL * i * k_i;
    }

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

brute.cpp 对每个节点都构造一次根到它的路径字符串，然后枚举所有子串，再判断这个子串是不是合法括号串。

这个做法很贴近题意，但复杂度太高。n 最大到 5 * 10^5，不能反复构造路径，更不能枚举每条路径上的所有子串。

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

从父亲 fa 走到当前节点 u 时，路径字符串只是在末尾多了一个字符。

因此 s_u 中的合法括号子串可以分成两类：

原来就在 s_fa 中的合法括号子串；
新增的、必须以 u 结尾的合法括号子串。

于是设：

end_count[u]：s_u 中以最后一个字符，也就是节点 u 结尾的合法括号子串数量；
total_count[u]：s_u 中所有合法括号子串数量，也就是题目里的 k_u。

那么一定有：

total\_count[u] = total\_count[fa] + end\_count[u]

现在问题变成：如何快速求 end_count[u]？

当前字符是左括号

如果节点 u 上是 (，那么没有合法括号串能以它结尾。

所以：

end\_count[u] = 0

当前字符是右括号

如果节点 u 上是 )，它想形成合法括号串，必须先在根到 u 的路径上找到一个还没有被匹配掉的 (。

设这个匹配到的左括号节点是 p。

那么最短的一个新增合法串是：

text

1p ... u

这贡献 1。

更进一步，如果在 p 的父亲位置还能接上一个“以 parent[p] 结尾的合法括号串”，那么拼起来仍然合法：

text

1[前面一个合法括号串] + [p ... u]

所以新增数量是：

end\_count[u] = end\_count[parent[p]] + 1

这一步是本题最关键的转移。

为什么只接 `end_count[parent[p]]`

因为一个以 u 结尾的合法括号串，最后一段一定是由 p 和 u 这对括号包住或闭合出来的。

如果它前面还要拼接别的合法串，那么这个合法串必须紧贴在 p 前面，也就是必须以 parent[p] 这个位置结尾。

不能随便接 total_count[parent[p]]，因为 total_count 里包含许多更早结束的子串，它们和 [p ... u] 中间隔着字符，拼不成一个连续子串。

用栈维护能匹配的左括号

沿着 DFS 当前路径走时，我们维护一个栈：

text

1open_stack = 当前根到 u 的路径上，尚未被匹配的左括号节点

进入一个节点时：

如果是 (，就把当前节点压栈；
如果是 ) 且栈非空，就弹出栈顶左括号 p，用它和当前右括号匹配；
如果是 ) 且栈为空，说明当前右括号不能作为任何新增合法串的结尾。

因为树有分叉，DFS 离开当前节点时必须恢复栈：

进入时压入的 (，离开时弹出；
进入时为了匹配 ) 弹出的 (，离开时要压回去。

这样每个节点进入一次、离开一次，整个过程是线性的。

样例过程

样例中括号串为：

text

11:'('  2:'('  3:')'  4:'('  5:')'

父亲关系为：

text

11 -> 2, 1 -> 3, 2 -> 4, 2 -> 5

几个关键节点如下：

节点	路径串	匹配情况	`end_count`	`total_count`
1	`(`	不能以 `(` 结尾	0	0
2	`((`	不能以 `(` 结尾	0	0
3	`()`	`3` 匹配 `1`	`end_count[0] + 1 = 1`	1
4	`(((`	不能以 `(` 结尾	0	0
5	`(()`	`5` 匹配 `2`	`end_count[1] + 1 = 1`	1

所以异或结果是：

3 \times 1 \oplus 5 \times 1 = 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106// main.cpp：用路径上的未匹配左括号栈，线性统计每个节点对应字符串中的合法括号子串数。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

struct Event {
    int type; // 0 表示进入节点，1 表示离开节点并恢复栈
    int u;
};

int n;
char bracket_char[MAXN];
int parent_node[MAXN];
int head[MAXN], to[MAXN], nxt[MAXN], edge_cnt;

long long end_count[MAXN];   // end_count[u]：根到 u 的字符串中，以 u 结尾的合法括号子串数量
long long total_count[MAXN]; // total_count[u]：根到 u 的字符串中所有合法括号子串数量

int action_type[MAXN];       // 1：进入时压入左括号；2：进入时弹出了一个左括号
int matched_open[MAXN];      // 当前右括号匹配到的左括号节点
vector<int> open_stack;      // 当前根到节点路径上尚未匹配的左括号节点

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void enter_node(int u, long long &answer) {
    action_type[u] = 0;
    matched_open[u] = 0;
    end_count[u] = 0;

    if (bracket_char[u] == '(') {
        open_stack.push_back(u);
        action_type[u] = 1;
    } else if (!open_stack.empty()) {
        int left_node = open_stack.back();
        open_stack.pop_back();

        matched_open[u] = left_node;
        action_type[u] = 2;

        // 形成一对 ( ... ) 后，可以接在 left_node 父亲处结尾的合法串后面。
        end_count[u] = end_count[parent_node[left_node]] + 1;
    }

    total_count[u] = total_count[parent_node[u]] + end_count[u];
    answer ^= 1LL * u * total_count[u];
}

void leave_node(int u) {
    if (action_type[u] == 1) {
        open_stack.pop_back();
    } else if (action_type[u] == 2) {
        open_stack.push_back(matched_open[u]);
    }
}

long long solve() {
    long long answer = 0;

    vector<Event> events;
    events.push_back({0, 1});

    while (!events.empty()) {
        Event cur = events.back();
        events.pop_back();

        int u = cur.u;
        if (cur.type == 0) {
            enter_node(u, answer);

            events.push_back({1, u});
            for (int e = head[u]; e != 0; e = nxt[e]) {
                events.push_back({0, to[e]});
            }
        } else {
            leave_node(u);
        }
    }

    return answer;
}

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

    cin >> n;
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        bracket_char[i] = s[i - 1];
    }

    for (int i = 2; i <= n; i++) {
        cin >> parent_node[i];
        add_edge(parent_node[i], i);
    }

    cout << solve() << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$ 。每个节点只进入、离开各一次。
空间复杂度： $O(n)$ 。需要存树、DP 数组、DFS 事件栈和当前路径上的左括号栈。

总结

这题难在不要真的去枚举路径上的所有子串。

核心拆法是：

text

1当前节点的总答案 = 父亲的总答案 + 以当前节点结尾的新增合法串数量

当当前节点是 ) 且匹配到左括号 p 时：

end\_count[u] = end\_count[parent[p]] + 1

这个式子只看“紧贴在 p 前面、并且以 parent[p] 结尾”的合法串，因此用的是 end_count，不是 total_count。

实现上，DFS 维护未匹配左括号栈，并在回溯时恢复现场，就能把每条根到节点路径都正确处理一遍。

本文的 main.cpp 已用逐路径枚举子串的 brute.cpp 进行 300 组随机树对拍。

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$	^

[CSP-S 2019] 括号树

目录

题意

思路

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

当前字符是左括号

当前字符是右括号

为什么只接 end_count[parent[p]]

用栈维护能匹配的左括号

样例过程

代码

复杂度

总结

为什么只接 `end_count[parent[p]]`