[CSP-S 2019] 括号树

知识点

树、括号匹配、动态规划、深度优先搜索

解题思路

对根到当前点的路径维护未匹配左括号栈。进入右括号点u时，若栈不空，弹出匹配的左括号v。令ending[u]为以u结尾的合法括号子串数，则ending[u]=ending[parent[v]]+1：匹配的(v,u)本身贡献1，也可接在parent[v]结尾的任意合法串后。total[u]=total[parent[u]]+ending[u]。遍历某子树结束后撤销该点对栈的修改，保证兄弟分支互不影响。代码用显式事件栈代替递归，避免五十万深链栈溢出。

正确性说明

左括号栈给出的v是唯一能与u作为最外层配对的最近未匹配左括号。任何以u结尾的合法串，都由(v,u)之间的合法部分及其前方零个或一个以parent[v]结尾的合法串拼接而成，这给出一一对应，故ending转移成立。路径新增的合法子串恰好是以u结尾的这些串，所以累加得到total。每个退出事件恢复原路径栈，因此所有节点都在正确的根路径状态下计算。最后按定义异或u*total[u]即为答案。

易错点

计数的是位置不同的子串；total与u*total都用64位整数。退出左括号点时弹出它；退出匹配成功的右括号点时重新压回此前弹出的左括号，不能遗漏回滚。无匹配右括号的ending为0。

复杂度

每个点进入、退出各一次，时间O(n)，树、状态数组及事件栈总空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Event{int u,matched;bool exit;};
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;string s;cin>>s;s=" "+s;
    vector<int> parent(n+1),left;
    vector<vector<int>> child(n+1);
    for(int u=2;u<=n;++u){cin>>parent[u];child[parent[u]].push_back(u);}
    vector<unsigned long long> ending(n+1),total(n+1);
    vector<Event> events;events.push_back({1,0,false});
    unsigned long long ans=0;
    while(!events.empty()){
        Event e=events.back();events.pop_back();int u=e.u;
        if(e.exit){
            if(s[u]=='(') left.pop_back();
            else if(e.matched) left.push_back(e.matched);
            continue;
        }
        int matched=0;
        if(s[u]=='(') left.push_back(u);
        else if(!left.empty()){
            matched=left.back();left.pop_back();
            ending[u]=ending[parent[matched]]+1;
        }
        total[u]=total[parent[u]]+ending[u];
        ans^=static_cast<unsigned long long>(u)*total[u];
        events.push_back({u,matched,true});
        for(auto it=child[u].rbegin();it!=child[u].rend();++it)
            events.push_back({*it,0,false});
    }
    cout<<ans<<'\n';
    return 0;
}