深入解析2019年CSP-S括号树问题（洛谷P5658）

一、问题背景

括号树是2019年CSP-S认证考试的压轴题，考察了树形结构、栈的应用以及动态规划的综合运用。题目要求计算树上所有合法括号子序列的异或和，是典型的树形DP问题。

二、核心思路

1. 树形结构处理：使用邻接表存储树结构

2. 括号匹配：通过栈结构维护当前路径的括号状态

3. 动态规划：

• dp[u]记录以u结尾的合法括号串数量

• sum[u]记录从根到u路径上的所有合法括号子序列和

三、完整代码解析

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 5e5 + 10;       // 最大节点数
vector<int> tree[MAXN];          // 树的邻接表表示
char s[MAXN];                    // 存储每个节点的括号字符
int fa[MAXN];                    // 父节点数组
long long dp[MAXN], sum[MAXN];   // DP数组和前缀和数组
stack<int> stk;                  // 用于括号匹配的栈

void dfs(int u) {
    int last = 0;                // 记录最近匹配的左括号位置
    if (s[u] == '(') {           // 遇到左括号
        stk.push(u);             // 压入栈中
    } else if (!stk.empty()) {   // 遇到右括号且栈非空
        last = stk.top();        // 取出栈顶左括号
        stk.pop();
        dp[u] = dp[fa[last]] + 1; // 状态转移：新增的合法串数=父节点的匹配数+1
    }
    
    sum[u] = sum[fa[u]] + dp[u]; // 计算前缀和（包含所有祖先的合法串数）
    
    for (int v : tree[u]) {      // 递归处理子节点
        dfs(v);
    }
    
    // 回溯处理（恢复栈状态）
    if (s[u] == '(') {           // 如果是左括号
        if (!stk.empty() && stk.top() == u) {
            stk.pop();           // 弹出当前节点（如果仍在栈顶）
        }
    } else if (last != 0) {      // 如果是成功匹配的右括号
        stk.push(last);          // 恢复之前弹出的左括号
    }
}

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    cin >> (s + 1);              // 从索引1开始读入括号序列
    
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];            // 读入父节点
        tree[fa[i]].push_back(i); // 构建树结构
    }
    
    dfs(1);                      // 从根节点开始DFS
    
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans ^= (i * sum[i]);     // 计算异或和
    }
    
    cout << ans << endl;
    return 0;
}

四、关键点解析

1. 栈的应用：实时维护当前路径的括号匹配状态

2. 回溯处理：确保DFS遍历子节点后恢复栈的原始状态

3. DP状态转移：dp[u] = dp[fa[last]] + 1体现了新增合法串的递推关系

4. 前缀和优化：sum[u]避免了重复计算，将时间复杂度优化到O(n)

五、常见错误

1. 未处理回溯导致栈状态错误

2. 忘记初始化根节点的父节点（fa[1]应为0）

3. 未使用long long导致计算结果溢出

参考：2019CSP-S括号树题解