复赛二：括号树(brackets)

洛谷：P5658
OJ：CSPS2019B

给定一棵有 n 个节点的树，每个节点上有一个括号（左括号 '(' 或右括号 ')'）。定义从根节点到节点 i 的路径上所有括号组成的字符串为 s_i。需要计算对于每个节点 i，s_i 中有多少个不同的子串是合法的括号串，然后计算所有 i* k_i 的异或和，其中 k_i 是 s_i 中不同的合法括号子串数。

变量说明

• n：树的节点数。
• brackets：一个字符串，存储每个节点上的括号，索引从 1 开始。
• tree：树的邻接表表示，tree[i] 是节点 i 的子节点列表。
• lst：lst[i] 表示以节点 i 结尾的、从根到节点 i 的路径中新增的合法括号子串数量。
• sum：sum[i] 表示从根到节点 i 的路径上所有不同的合法括号子串的数量。
• fa：fa[i] 表示节点 i 的父节点编号。
• s：一个栈，用于匹配括号，存储左括号的位置。
• ans：最终的异或和结果。

算法流程

1. 读取输入并初始化数据结构
   • 读取节点数 n 和括号串 brackets，并在开头添加一个空格以使索引从 1 开始。
   • 初始化各个数组和数据结构的大小为 n + 1，以便使用 1-based 索引。
   • 读取每个节点的父节点信息，建立树的邻接表 tree，并记录父节点 fa[i]。
2. 深度优先搜索（DFS）遍历树从根节点开始，对树进行 DFS 遍历。DFS 函数的核心逻辑如下：
   • 括号匹配与合法子串计数
     • 如果当前节点的括号是右括号 ')'，并且栈不为空，则栈顶元素为匹配的左括号位置 matchedLeft。
       • 更新 lst[node] = lst[fa[matchedLeft]] + 1，表示以当前节点为结尾的新增合法子串数量。
       • 弹出栈顶元素，表示匹配完成。
     • 如果当前节点的括号是左括号 '('，则将当前节点编号压入栈中。
   • 更新合法子串总数
     • sum[node] = sum[fa[node]] + lst[node]，表示从根到当前节点的路径上，所有不同的合法括号子串总数。
   • 递归遍历子节点
     • 对于当前节点的每个子节点，递归调用 DFS 函数。
   • 回溯操作（状态恢复）
     • 为了在回溯时维护正确的栈状态：
       • 如果在当前节点匹配到了左括号（即 matchedLeft != 0），在回溯时将其重新压回栈中。
       • 如果当前节点是左括号 '('，在回溯时将其从栈中弹出。
3. 计算异或和遍历所有节点，计算 ans ^= sum[i] * i，即每个节点编号乘以其对应的合法子串数量，然后进行异或累积。
4. 输出结果输出最终计算的异或和 ans。

算法原理详解

• 括号匹配与合法子串计数
  • 使用栈 s 来模拟括号匹配的过程。左括号 '(' 入栈，右括号 ')' 尝试与栈顶的左括号匹配。
  • 当匹配成功时，形成了一个新的合法括号子串，其起始位置为匹配的左括号的位置，结束位置为当前右括号的位置。
  • 为了计算不同的合法子串数量，利用以匹配的左括号父节点为结尾的合法子串数量 lst[fa[matchedLeft]]，加上当前新匹配的括号对所形成的新合法子串数量 1，得到 lst[node] = lst[fa[matchedLeft]] + 1。
• 合法子串总数的累积
  • sum[node] 包含了从根节点到当前节点的路径上，所有不同的合法括号子串数量。
  • 通过 sum[node] = sum[fa[node]] + lst[node]，将父节点的总数与当前节点新增的数量累加。
• 避免重复计数
• 通过使用 lst[fa[matchedLeft]]，确保只计数到 matchedLeft 的父节点为止，避免了重复计数包含 matchedLeft 本身的合法子串。这样可以保证每个合法子串都是独特的，符合题目中“不同的子串”的定义。
• 栈状态的维护
  • 在递归遍历过程中，栈的状态反映了当前路径上未匹配的左括号。
  • 回溯时，通过适当的操作（如重新压入匹配的左括号或弹出当前左括号），确保栈的状态与当前路径对应。确保在遍历其他分支时，括号匹配的过程不受之前分支的影响。

示例：

5
(()()
1 1 2 2

节点 1

• 括号为 '('，入栈。
• lst[1] = 0（无匹配）。
• sum[1] = sum[0] + lst[1] = 0 + 0 = 0。

节点 2

• 括号为 ')'，栈不为空，匹配成功，匹配的左括号在节点 1。
• lst[2] = lst[fa[1]] + 1 = lst[0] + 1 = 1。
• sum[2] = sum[fa[2]] + lst[2] = sum[1] + 1 = 0 + 1 = 1。

节点 3

• 括号为 '('，入栈。
• lst[3] = 0（无匹配）。
• sum[3] = sum[fa[3]] + lst[3] = sum[1] + 0 = 0 + 0 = 0。

节点 4

• 括号为 ')'，栈不为空，匹配成功，匹配的左括号在节点 3。
• lst[4] = lst[fa[3]] + 1 = lst[1] + 1 = 0 + 1 = 1。
• sum[4] = sum[fa[4]] + lst[4] = sum[3] + 1 = 0 + 1 = 1。

ans = (1 * sum[1]) ^ (2 * sum[2]) ^ (3 * sum[3]) ^ (4 * sum[4]) = (1 * 0) ^ (2 * 1) ^ (3 * 0) ^ (4 * 1) = 0 ^ 2 ^ 0 ^ 4 = 6

算法复杂度分析

• 时间复杂度
  • DFS 遍历每个节点一次，匹配括号和更新栈的操作均为 $O(1)$，因此总时间复杂度为 $O(n)$。
• 空间复杂度
  • 使用了额外的栈和数组，空间复杂度为 $O(n)$。

代码实现：

 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

/**************************************************************** 
 * Description: 2019_S_semi_2  括号树
 * Author: Alex Li
 * Date: 2024-09-21 11:22:21
 * LastEditTime: 2024-09-29 09:35:35
****************************************************************/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n; // 树的节点数量
string brackets; // 使用string存储括号串，方便操作
vector<vector<int>> tree; // 用vector来存储树的邻接表
vector<long long> lst, sum; // lst存储每个节点对应的合法子串数，sum存储路径上所有子串数的累积
vector<int> fa; // fa[i]表示节点i的父节点
stack<int> s; // 使用标准库的stack模拟栈
long long ans; // 最终异或和结果
                                                                                               
// 深度优先搜索遍历树
void dfs(int node) {
    int matchedLeft = 0;
    if (brackets[node] == ')') {
        if (!s.empty()) { // 当前节点是右括号且栈不为空，说明有匹配的左括号
            matchedLeft = s.top();
            lst[node] = lst[fa[matchedLeft]] + 1; // 更新当前节点的合法子串数
            s.pop(); // 弹出栈顶
        }
    } else if (brackets[node] == '(') {
        s.push(node); // 当前节点是左括号，入栈
    }

    sum[node] = sum[fa[node]] + lst[node]; // 更新当前节点的合法子串数累积值

    // 遍历当前节点的所有子节点
    for (int child : tree[node]) {
        dfs(child); // 递归子节点
    }

    // 回溯复原操作
    if (matchedLeft != 0) {
        s.push(matchedLeft); // 恢复被弹出的元素
    } else if (brackets[node] == '(' && !s.empty()) {
        s.pop(); // 当前节点是左括号，恢复状态
    }
}

int main() {
    //freopen("brackets.in","r",stdin);
    //freopen("brackets.out","w",stdout);
    cin >> n; // 输入树的节点数
    brackets.resize(n + 1); // 动态调整括号串大小
    tree.resize(n + 1); // 动态调整树的邻接表大小
    lst.resize(n + 1); // 动态调整lst数组大小
    sum.resize(n + 1); // 动态调整sum数组大小
    fa.resize(n + 1); // 动态调整fa数组大小
     cin >> brackets; // 直接读取整个括号串
   brackets = " " + brackets; // 在括号串前面加一个空格，保证从1开始索引1个节点开始
            
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent; // 输入每个节点的父节点
       tree[parent].push_back(i);
       
        fa[i] = parent; // 记录父节点
    }
    dfs(1); // 从根节点开始DFS
    for (int i = 1; i <= n; i++) 
        ans ^= sum[i] *i; // 计算异或和
    
    cout << ans << endl; // 输出结果
    return 0;
}