括号树 题解

题目分析

这道题要求计算树上每个节点到根路径形成的括号串中，不同合法括号子串的数量，并求加权异或和。

关键点：

• 树结构，每个节点有一个括号
• 需要处理从根到每个节点的路径形成的括号串
• 统计该串中不同合法括号子串的数量

解题思路

核心观察

1. 合法括号串性质：合法的括号串需要左右括号匹配
2. 树上路径：从根到节点的路径是唯一的
3. 动态规划：可以利用父节点的信息计算子节点的答案

算法设计

代码采用了树形DP + 括号匹配的方法：

主要思路：

1. 括号匹配：遇到右括号时，尝试找到与之匹配的左括号
2. 状态转移：利用KMP思想在树上进行括号匹配
3. 答案累积：当前节点的合法子串数 = 匹配成功的数量 + 父节点的累积数量

代码详解

#include <bits/stdc++.h>
using namespace std;

const int max_n = 5e5 + 5;
int f[max_n];      // 父节点数组
char str[max_n];   // 每个节点的括号
int dp[max_n];     // 记录匹配的左括号位置
long long ans[max_n]; // 每个节点的答案

int main() {
    int n;
    scanf("%d", &n);
    
    // 读入括号串
    while (str[1] != '(' && str[1] != ')')
        str[1] = getchar();
    for (int i = 2; i <= n; ++i)
        str[i] = getchar();
    
    // 读入父节点信息
    for (int i = 2; i <= n; ++i)
        scanf("%d", &f[i]);
    
    long long Ans = 0;
    
    // 处理每个节点
    for (int i = 1; i <= n; ++i) {
        if (str[i] == ')') {
            int x = f[i];  // 从父节点开始找匹配
            
            // 沿着失败指针找可能的左括号
            while (x && str[x] != '(')
                x = f[dp[x]];
            
            if (x) {  // 找到了匹配的左括号
                dp[i] = x;  // 记录匹配关系
                // 当前匹配贡献1，加上匹配左括号的父节点的贡献
                ans[i] = ans[f[x]] + 1;
            }
        }
    }
    
    // 累加答案并计算异或和
    for (int i = 1; i <= n; ++i) {
        ans[i] += ans[f[i]];  // 加上父节点的累积答案
        Ans ^= 1ll * i * ans[i];
    }
    
    printf("%lld", Ans);
    return 0;
}

算法原理详解

1. 括号匹配机制

当遇到右括号 ) 时：

• 从当前节点的父节点开始向上查找
• 如果找到左括号 (，则形成匹配
• 使用类似KMP的失败指针机制高效查找

2. DP状态含义

• dp[i]：如果节点i是右括号，记录与之匹配的左括号节点；否则为0
• ans[i]：以节点i结尾的路径中，新增的合法括号子串数量

3. 答案计算

对于节点i：

1. 直接匹配：如果当前形成新的匹配，贡献+1
2. 继承父节点：ans[i] += ans[f[i]] 继承父节点的所有合法子串

4. 关键代码解析

while (x && str[x] != '(')
    x = f[dp[x]];

这行代码实现了高效的括号匹配：

• 如果当前节点不是左括号，沿着失败链继续找
• dp[x] 记录了之前匹配的信息，避免重复计算

复杂度分析

• 时间复杂度：O(n)，每个节点最多被访问常数次
• 空间复杂度：O(n)，存储树结构和DP数组

样例解析

以样例为例：

5
(()()
1 1 2 2

树结构：

1( -- 2( -- 4(
  \-- 3) -- 5)

处理过程：

• 节点1: (，无匹配
• 节点2: ((，无匹配
• 节点3: ()，匹配成功，ans[3] = 1
• 节点4: (((，无匹配
• 节点5: (()，匹配成功，ans[5] = 1

最终计算：

• k1=0, k2=0, k3=1, k4=0, k5=1
• 异或和：1×0 ⊕ 2×0 ⊕ 3×1 ⊕ 4×0 ⊕ 5×1 = 3 ⊕ 5 = 6

关键技巧

1. 失败指针：类似KMP的next数组，高效处理括号匹配
2. 树形DP：利用树结构自顶向下传递信息
3. 增量计算：只计算新增的合法子串，避免重复统计
4. 异或运算：直接计算最终结果，避免存储大量中间数据

总结

这道题的解题亮点：

1. 问题转化：将括号匹配问题转化为树上的动态规划
2. 高效匹配：使用失败指针机制避免暴力匹配
3. 增量统计：只关注新增的合法子串，优化计算
4. 简洁实现：用少量状态完成复杂统计

算法通过巧妙的DP设计和失败指针机制，在O(n)时间内解决了树上括号匹配计数问题，展示了处理树形结构复杂问题的有效方法。