[CSP-S 2019 T2] 括号树

题意

给定一颗 n 个节点的树，每个节点有一个括号 ( 或者 )，现在询问 i 节点到根节点这一条链上所有括号组成的括号序列有几个子括号序列合法

对题目进行分析

观察 1

定义 f(x) 为以 x 节点结尾的合法括号序列数，很容易想到 $[1,i]$ 链上的子括号合法子序列数 为

\[ \sum_{e \in [1,i]}{f(e)} \]

所以问题转化到了如何快速求出所有 f(x)，这是一个十分重要的转化，因为后面都是基于 f(x) 的求解展开的

观察 2

考虑一个括号序列是否合法的条件:
一个很常见的套路：将 ( 转为 1，) 转为 −1
定义 ai 为 i 号节点上的权值，fai 为 i 号节点的父节点编号

\[ \forall x \in [i, j], \sum_{e \in [i,x]}{a_e} \ge 0 \]

\[ \sum_{e \in [i,j]}{a_e} = 0 \]

很明显这两个式子的计算可以用 树上前缀和 加速

定义

\[ s_i = \sum_{e \in [1,i]} a_i \]

第一个式子 Equation 1

则上面的第一个式子可以改写成

\[ \forall x \in [i, j], s_x - s_{fa_i} \ge 0 \]

也就是

\[ \forall x \in [i, j], s_x \ge s_{fa_i} \]

对于任意的 $fa_i$，$j$ 的取值必须保证 $s_i \sim s_j$ 没有一个元素小于 $s_{fa_i}$
$\therefore$ $s_{fa_i}$ 是 $[i,j]$ 中最小的元素
$\therefore$ 当 $i$ 固定时 $j$ 的右边界是 $s_{fa_i}$ 右侧第一个小于 $s_{fa_i}$ 的元素

现在思路就显而易见了

这个式子可以使用 单调栈 快速维护

在 dfs 树的时候，只需要维护一个当前链的单调栈，栈中的即还没有找到答案的元素即是当前元素 $j$ 的可选 $fa_i$。

第二个式子 Equation 2

第二个式子用前缀和表达就是

\[ s_j - s_{fa_i} = 0 \]

也就是说当前元素 $s_j$ 必须和 $s_i$ 相等，这大大缩小了我们的 $i$ 的范围，统计答案的时候不能把栈中元素全部加上，只能选等于 $s_j$ 的，由于栈是 非严格单调递增的，可选答案只能排在栈顶或没有，于是我们要记录 每个元素向下有多少个连续相等的，记为 $cnt_k$，$k$ 为元素的高度，因为我们在维护单调栈时 pop 操作会更新栈顶元素，所以前面元素的 $cnt$ 值也会用到。

梳理思路

使用 bfs 遍历树
遍历过程中维护单调栈
在遇到一个新元素 $s_i$ 时先 pop 栈中元素直到所有元素都 $\le s_i$，同时更新栈顶的 $cnt$ 值
如果 $s_i$ 和栈顶元素相等，则 $f(x) = cnt_{top}$ 否则 $f(x) = 0$
将 $s_i$ 压入栈并更新 $cnt$ 数组
下一层递归
回溯 *注意，$cnt$ 和单调栈都要回溯
回到步骤3，处理下一个元素

下一步呢？

获取完 $f(x)$ 之后就简单了，通过

\[ ans_i = \sum_{e \in [1,i]}{f(e)} \]

就可以算出 $ans_i$，按题目输出即可。（记得开 long long）

代码复杂度

时间： $O(n)$，空间： $O(n)$

注意事项

初始化

开始求 $f(x)$ 之前要先求出 $s_i$，使用 dfs 递推即可

\[ s_i = s_{fa_i} + a_i \]

求 $f(x)$ 的递归起点为 $1$，要先将 $0，1$ 压入栈并且更新 $cnt$ 数组（$0$ 是因为 $fa_1 = 0$ 也要考虑有全链合法的情况，$1$ 是因为递归起点为 $1$，必须处理好 $1$ 再开始递归）

回溯

回溯的时候要格外小心空间和时间~~比赛时调了 2.5h~~

代码示例

Deepseek 代码参考:

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

const int N = 500005;
int n, fa[N], a[N], s[N];
char br[N];
vector<int> g[N];
long long f[N], ans[N];
vector<int> st;
long long cnt[N];

void dfs(int u) {
    for (int t : g[u]) {
        vector<int> popped;
        vector<pair<int,long long>> saved;

        while (!st.empty() && s[st.back()] > s[t]) {
            int sz = st.size();
            saved.push_back({sz, cnt[sz]});
            cnt[sz] = 0;
            popped.push_back(st.back());
            st.pop_back();
        }

        int p = st.size();
        if (!st.empty() && s[st.back()] == s[t]) {
            f[t] = cnt[p];
            cnt[p + 1] = cnt[p] + 1;
        } else {
            f[t] = 0;
            cnt[p + 1] = 1;
        }

        st.push_back(t);
        ans[t] = ans[fa[t]] + f[t];

        dfs(t);

        st.pop_back();
        for (int i = (int)popped.size() - 1; i >= 0; i--)
            st.push_back(popped[i]);
        for (auto &pr : saved)
            cnt[pr.first] = pr.second;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> (br + 1);
    for (int i = 1; i <= n; i++) a[i] = (br[i] == '(') ? 1 : -1;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        g[fa[i]].push_back(i);
    }

    s[0] = 0;
    for (int i = 1; i <= n; i++) s[i] = s[fa[i]] + a[i];

    st.push_back(0);
    st.push_back(1);
    cnt[1] = cnt[2] = 1;

    f[1] = 0;
    ans[1] = 0;

    dfs(1);

    long long res = 0;
    for (int i = 1; i <= n; i++) res ^= 1LL * i * ans[i];
    cout << res << '\n';
    return 0;
}

赛时代码：

#include <bits/stdc++.h>
#define int long long
using namespace std; 
const int N = 5e5+5;
int a[N], s[N], ans[N], fa[N], ansf;
vector<int> v[N];
void get_s(int x){
    s[x] = s[fa[x]] + a[x];
    for(int t : v[x]){
        get_s(t);
    }
}

struct op{
    int x, v;
};

vector<int> st;
int cnt[N];

void get_r(int x){
    for(int t : v[x]){

        vector<int>tmp;
        vector<op> ops;
        while(!st.empty() && s[st[st.size()-1]] > s[t]) {
            tmp.push_back(st[st.size()-1]);
            ops.push_back({st.size(), cnt[st.size()]});
            cnt[st.size()] = 0;
            st.pop_back();
        }
        if(!st.empty() && s[st[st.size()-1]] == s[t]){
            ans[t]+=cnt[st.size()];
            cnt[st.size()+1] = cnt[st.size()]+1;
        } else {
            cnt[st.size()+1] = 1;
        }
        st.push_back(t);

        get_r(t);
        st.pop_back();
        cnt[st.size()+1] = 1;
        while(!tmp.empty()){
            st.push_back(tmp[tmp.size()-1]);
            tmp.pop_back();
        }
        while(!ops.empty()){
            cnt[ops[ops.size()-1].x] = ops[ops.size()-1].v;
            ops.pop_back();
        }
    }
}

void get_ans(int x){
    ans[x] += ans[fa[x]];
    ansf ^= (x * ans[x]);
    for(int t : v[x]){
        get_ans(t); 
    }
}
signed main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        char c;
        cin >> c;
        if(c == '(') a[i] = 1;
        if(c == ')') a[i] = -1; 
    }
    for(int i = 2;i <= n;i++){
        int f;
        cin >> f;
        v[f].push_back(i);
        fa[i] = f;
    } 

    get_s(1);

    st.push_back(0);
    st.push_back(1);
    cnt[1] = cnt[2] = 1;

    get_r(1);

    get_ans(1);

    cout << ansf;
}