洛谷-P5658 [CSP-S 2019] 括号树 题解
值域线段树 + 离线的O(nlogn)O(n\log n)O(nlogn)做法。
题目大意
给定一棵树，每个节点有一个括号。对于每个节点iii，定义sis_isi为从根节点到iii的路径上所有括号按顺序组成的字符串。求每个sis_isi中互不相同的合法括号子串的个数kik_iki。
思路
首先，kik_iki可以从父节点递推得到，ki=kfi+aik_i=k_{f_i}+a_iki=kfi+ai。其中aia_iai为以节点iii结尾的合法括号序列数量。因此只要求出每个节点的aaa。
经典技巧，将(\texttt{(}(的权值设为111，)\texttt{)})设为−1−1−1，做树上前缀和。设点uuu的前缀和为sumusum_usumu。则以uuu结尾的合法括号子串的开头vvv必须满足：
- sumfv=sumusum_{f_v}=sum_usumfv=sumu。
- 对于v→uv\to uv→u这条链上的所有点xxx，有sumx≥sumusum_x\ge sum_usumx≥sumu。
在 DFS 过程中开一棵值域线段树维护1→u1\to u1→u这条链上每个sumsumsum值对应的最大节点深度。这样就能找到sump<sumusum_p<sum_usump<sumu且深度最大的节点ppp。
设ask(x,y)ask(x,y)ask(x,y)表示1→x1\to x1→x链上sum=ysum=ysum=y的节点数量。则au=ask(fu,k)−ask(p,k)a_u=ask(f_u,k)-ask(p,k)au=ask(fu,k)−ask(p,k)。
第一遍 DFS 求出所有询问并离线下来。
第二遍 DFS 求出所有点的aaa。
第三遍 DFS 对aaa做树上前缀和得到所有点的kkk即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn)。
Code
#include<bits/stdc++.h>#definerept(i,a,b)for(inti(a);i<=b;++i)#definels(p)((p)<<1)#definers(p)((p)<<1|1)#defineebemplace_back#defineintlonglongusingnamespacestd;constexprintN=5e5+5;structQuery{intk,coef,id;// k：目标值// coef：贡献系数，1/-1// id：贡献给到的节点Query(int_k,int_coef,int_id):k(_k),coef(_coef),id(_id){}};structSegTree{intt[N<<3];voidupdate(intp,intpl,intpr,intpos,intx){// 单点修改if(pl==pr)returnvoid(t[p]=x);intmid=pl+pr>>1;if(pos<=mid)update(ls(p),pl,mid,pos,x);elseupdate(rs(p),mid+1,pr,pos,x);t[p]=max(t[ls(p)],t[rs(p)]);}intquery(intp,intpl,intpr,intl,intr){// 区间maxif(l>r)return0;if(l<=pl&&pr<=r)returnt[p];intmid=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));returna;}}sgt;chars[N];intsum[N],dep[N],cnt[N<<1],a[N],st[N];intn,m,ans;vector<int>g[N];vector<Query>q[N];voiddfs1(intu){intlst=sgt.query(1,1,m,sum[u],sum[u]);sgt.update(1,1,m,sum[u],dep[u]);st[dep[u]]=u;for(intv:g[u]){sum[v]=sum[u]+(s[v]=='('?1:-1);dep[v]=dep[u]+1;if(s[v]==')'){intbound=sgt.query(1,1,m,1,sum[v]-1);q[u].eb(sum[v],1,v);if(bound)q[st[bound]].eb(sum[v],-1,v);}dfs1(v);}sgt.update(1,1,m,sum[u],lst);}voiddfs2(intu){++cnt[sum[u]];for(Query x:q[u]){a[x.id]+=x.coef*cnt[x.k];}for(intv:g[u])dfs2(v);--cnt[sum[u]];}voiddfs3(intu){for(intv:g[u]){a[v]+=a[u];dfs3(v);}ans^=u*a[u];}signedmain(){cin.tie(0)->sync_with_stdio(0);cin>>n>>s+1;m=n<<1;rept(i,2,n){intx;cin>>x;g[x].eb(i);}g[0].eb(1);sum[0]=n,dep[0]=1;// 为了不出负数，sum统一加上ndfs1(0),dfs2(0),dfs3(0);cout<<ans;return0;}