2019 括号树 · 方案二栈加 DFS 递推

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1695 字

一遍 DFS 用栈递推，每个点的答案由子节点拼出

2019
树

正文

// CSP-S 2019 复赛 T2 · 括号树（方案二：栈 + DFS 递推，满分 O(n)）
// 原题：https://oj.yecheng.tv/p/CSPS2019B
// 题意：同方案一。
// 思路（一遍 DFS 递推）：
//   s_i 只是 s_fa(i) 末尾多一个字符，于是 a_i = a_fa(i) + c_i，
//   其中 c_i = "右端点在 i、新配上的那一对"能延续的合法段对数。
//   DFS 时用一个下标栈维护根到当前点的未匹配括号：
//   - 遇 '('：下标入栈，c_i = 0；
//   - 遇 ')' 且栈非空：弹出栈顶 t（祖先的某个 '('），
//       c_i = c_fa(t) + 1
//     —— 新增这一对，且紧挨在 t 之前的合法段全部可拼接
//     （c 递推天然承接"()..."型拼接效应）；
//   - 遇 ')' 且栈空：配不上，c_i = 0。
//   回溯时还原栈：进栈的弹出、弹出的压回 memo。
//   答案：DFS 进入 u 时先 cur ^= u * a_u，前缀异或和逐层传递。
// 复杂度：O(n)。
// 易错点：
//   1. c 的承接对象是"被弹出左括号所在点的父亲"的 c，不是栈顶；
//   2. 异或顺序：先更新 cur 再累计到 sum（sum 即到达每个点时的值）；
//   3. a、sum 用 unsigned long long（u * a_u 最坏 ~1.25e11）；
//   4. 回溯还原别写反：'(' 回溯 top--，')' 回溯把 memo 压回。
#include <cstdio>
#include <vector>
using namespace std;

int n, par[500005];
char ch[500005];
long long c[500005], a[500005];
vector<int> g[500005];
int stk[500005], top = 0;
unsigned long long sum = 0;

void dfs(int u, unsigned long long cur) {
    int memo = -1;
    if (ch[u] == '(') {
        stk[++top] = u;
    } else if (top > 0) {
        memo = stk[top--];
        c[u] = (par[memo] == 0) ? 1 : c[par[memo]] + 1;
    } else {
        c[u] = 0;
    }
    a[u] = (u == 1) ? c[u] : a[par[u]] + c[u];
    cur ^= (unsigned long long)u * a[u];
    sum ^= cur;
    for (int v : g[u]) dfs(v, cur);
    if (ch[u] == '(') top--;
    else if (memo != -1) stk[++top] = memo;
}

int main() {
    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout);
    scanf("%d", &n);
    scanf("%s", ch + 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &par[i]);
        g[par[i]].push_back(i);
    }
    dfs(1, 0);
    printf("%llu\n", sum);
    return 0;
}

2019 括号树 · 方案二 栈加 DFS 递推

正文

CSP-S 标程 · 复赛真题的其它内容

2019 括号树 · 方案二栈加 DFS 递推