洛谷-P5658 [CSP-S 2019] 括号树题解

通达世海 發表於 2025-11-22 20:01:00

值域线段树 + 离线的 \(O(n\log n)\) 做法。
<h2 id="题目大意">题目大意</h2>
给定一棵树，每个节点有一个括号。对于每个节点 \(i\)，定义 \(s_i\) 为从根节点到 \(i\) 的路径上所有括号按顺序组成的字符串。求每个 \(s_i\) 中互不相同的合法括号子串的个数 \(k_i\)。
<h2 id="思路">思路</h2>
首先，\(k_i\) 可以从父节点递推得到，\(k_i=k_{f_i}+a_i\)。其中 \(a_i\) 为以节点 \(i\) 结尾的合法括号序列数量。因此只要求出每个节点的 \(a\)。
经典技巧，将 \(\texttt{(}\) 的权值设为 \(1\)，\(\texttt{)}\) 设为 \(−1\) ，做树上前缀和。设点 \(u\) 的前缀和为 \(sum_u\)。则以 \(u\) 结尾的合法括号子串的开头 \(v\) 必须满足：
<ol>
<li>\(sum_{f_v}=sum_u\)。</li>
<li>对于 \(v\to u\) 这条链上的所有点 \(x\)，有 \(sum_x\ge sum_u\)。</li>
</ol>
在 DFS 过程中开一棵值域线段树维护 \(1\to u\) 这条链上每个 \(sum\) 值对应的最大节点深度。这样就能找到 \(sum_p<sum_u\) 且深度最大的节点 \(p\)。
设 \(ask(x,y)\) 表示 \(1\to x\) 链上 \(sum=y\) 的节点数量。则 \(a_u=ask(f_u,k)-ask(p,k)\)。
第一遍 DFS 求出所有询问并离线下来。
第二遍 DFS 求出所有点的 \(a\)。
第三遍 DFS 对 \(a\) 做树上前缀和得到所有点的 \(k\) 即可。
时间复杂度 \(O(n\log n)\)。
<h2 id="code">Code</h2>
<pre><code class="language-cpp">#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define eb emplace_back
#define int long long
using namespace std;
constexpr int N=5e5+5;
struct Query{
int k,coef,id;
// k：目标值
// coef：贡献系数，1/-1
// id：贡献给到的节点
Query(int _k,int _coef,int _id):k(_k),coef(_coef),id(_id){}
};
struct SegTree{
int t;
void update(int p,int pl,int pr,int pos,int x){// 单点修改
 if(pl==pr) return void(t=x);
 int mid=pl+pr>>1;
 if(pos<=mid) update(ls(p),pl,mid,pos,x);
 else update(rs(p),mid+1,pr,pos,x);
 t=max(t,t);
}
int query(int p,int pl,int pr,int l,int r){// 区间max
 if(l>r) return 0;
 if(l<=pl&&pr<=r) return t;
 int mid=pl+pr>>1,a=0;
 if(l<=mid) a=max(a,query(ls(p),pl,mid,l,r));
 if(mid<r) a=max(a,query(rs(p),mid+1,pr,l,r));
 return a;
}
}sgt;
char s;
int sum,dep,cnt,a,st;
int n,m,ans;
vector<int> g;
vector<Query> q;
void dfs1(int u){
int lst=sgt.query(1,1,m,sum,sum);
sgt.update(1,1,m,sum,dep);
st]=u;
for(int v:g){
 sum=sum+(s=='('?1:-1);
 dep=dep+1;
 if(s==')'){
 int bound=sgt.query(1,1,m,1,sum-1);
 q.eb(sum,1,v);
 if(bound) q].eb(sum,-1,v);
 }
 dfs1(v);
}
sgt.update(1,1,m,sum,lst);
}
void dfs2(int u){
++cnt];
for(Query x:q){
 a+=x.coef*cnt;
}
for(int v:g) dfs2(v);
--cnt];
}
void dfs3(int u){
for(int v:g){
 a+=a;
 dfs3(v);
}
ans^=u*a;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>s+1;
m=n<<1;
rept(i,2,n){
 int x;cin>>x;
 g.eb(i);
}
g.eb(1);
sum=n,dep=1;// 为了不出负数，sum统一加上n
dfs1(0),dfs2(0),dfs3(0);
cout<<ans;
return 0;
}
</code></pre> 
来源：https://www.cnblogs.com/xiaoniu142857/p/19258500

頁: [1]

琼殿技术论坛's Archiver

洛谷-P5658 [CSP-S 2019] 括号树 题解

洛谷-P5658 [CSP-S 2019] 括号树题解