当前位置：首页 > 提高组 > 【CSP-S 2019】括号树（洛谷P5658）解题报告：栈+DFS+异或优化详解

【CSP-S 2019】括号树（洛谷P5658）解题报告：栈+DFS+异或优化详解

2个月前 (06-13)

一、题目解读

括号树问题（洛谷P5658）要求处理一个由括号序列转化的树结构：每个节点表示一个括号，'('为子节点，')'为父节点。题目给定一棵n个节点的树，需计算每个节点的深度（括号层数），并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为树，并高效计算深度信息。

二、解题思路

采用“栈+深度优先搜索（DFS）”的策略：

1. 栈处理括号匹配：用栈维护未匹配的左括号，遇到')'时弹出栈顶，建立父子关系。

2. 树构建与深度计算：通过父节点输入建立树结构，DFS遍历时利用栈弹出更新深度（dp值）。

3. 累积深度和：sum数组记录子树深度总和，避免重复计算。

4. 异或求解：最终遍历所有节点，异或乘积i*sum[i]得到答案。

三、解题步骤

1. 输入处理：读入n、括号序列s及父节点数组fa，构建树边tree。

2. DFS遍历：从根节点1开始，递归处理子节点：

遇到'('入栈，')'时弹出并更新dp（深度继承父节点+1）。

累加sum：sum[u] = sum[父节点] + dp[u]。

3. 异或计算：遍历节点i，异或值i*sum[i]累加至ans。

四、代码与注释

#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]; // 深度、子树深度和
stack<int> stk; // 存储未匹配左括号

void dfs(int u) { // 递归遍历节点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); // 读入括号序列（从s[1]开始）
    
    for (int i = 2; i <= n; ++i) { // 建立树边（从2开始）
        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;
}