值域线段树 离线的O(nlog⁡n)O(n\log n)O(nlogn)做法。题目大意给定一棵树每个节点有一个括号。对于每个节点iii定义sis_isi​为从根节点到iii的路径上所有括号按顺序组成的字符串。求每个sis_isi​中互不相同的合法括号子串的个数kik_iki​。思路首先kik_iki​可以从父节点递推得到kikfiaik_ik_{f_i}a_iki​kfi​​ai​。其中aia_iai​为以节点iii结尾的合法括号序列数量。因此只要求出每个节点的aaa。经典技巧将(\texttt{(}(的权值设为111)\texttt{)})设为−1−1−1做树上前缀和。设点uuu的前缀和为sumusum_usumu​。则以uuu结尾的合法括号子串的开头vvv必须满足sumfvsumusum_{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值对应的最大节点深度。这样就能找到sumpsumusum_psum_usump​sumu​且深度最大的节点ppp。设ask(x,y)ask(x,y)ask(x,y)表示1→x1\to x1→x链上sumysumysumy的节点数量。则auask(fu,k)−ask(p,k)a_uask(f_u,k)-ask(p,k)au​ask(fu​,k)−ask(p,k)。第一遍 DFS 求出所有询问并离线下来。第二遍 DFS 求出所有点的aaa。第三遍 DFS 对aaa做树上前缀和得到所有点的kkk即可。时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)。Code#includebits/stdc.h#definerept(i,a,b)for(inti(a);ib;i)#definels(p)((p)1)#definers(p)((p)1|1)#defineebemplace_back#defineintlonglongusingnamespacestd;constexprintN5e55;structQuery{intk,coef,id;// k目标值// coef贡献系数1/-1// id贡献给到的节点Query(int_k,int_coef,int_id):k(_k),coef(_coef),id(_id){}};structSegTree{intt[N3];voidupdate(intp,intpl,intpr,intpos,intx){// 单点修改if(plpr)returnvoid(t[p]x);intmidplpr1;if(posmid)update(ls(p),pl,mid,pos,x);elseupdate(rs(p),mid1,pr,pos,x);t[p]max(t[ls(p)],t[rs(p)]);}intquery(intp,intpl,intpr,intl,intr){// 区间maxif(lr)return0;if(lplprr)returnt[p];intmidplpr1,a0;if(lmid)amax(a,query(ls(p),pl,mid,l,r));if(midr)amax(a,query(rs(p),mid1,pr,l,r));returna;}}sgt;chars[N];intsum[N],dep[N],cnt[N1],a[N],st[N];intn,m,ans;vectorintg[N];vectorQueryq[N];voiddfs1(intu){intlstsgt.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])){intboundsgt.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);cinns1;mn1;rept(i,2,n){intx;cinx;g[x].eb(i);}g[0].eb(1);sum[0]n,dep[0]1;// 为了不出负数sum统一加上ndfs1(0),dfs2(0),dfs3(0);coutans;return0;}