思路首先kiki 可以从父节点递推得到kikfiaikikfiai。其中 aiai 为以节点 ii 结尾的合法括号序列数量。因此只要求出每个节点的 aa。经典技巧将 (( 的权值设为 11)) 设为 −1−1 做树上前缀和。设点 uu 的前缀和为 sumusumu。则以 uu 结尾的合法括号子串的开头 vv 必须满足sumfvsumusumfvsumu。对于 v→uv→u 这条链上的所有点 xx有 sumx≥sumusumx≥sumu。在 DFS 过程中开一棵值域线段树维护 1→u1→u 这条链上每个 sumsum 值对应的最大节点深度。这样就能找到 sumpsumusumpsumu 且深度最大的节点 pp。设 ask(x,y)ask(x,y) 表示 1→x1→x 链上 sumysumy 的节点数量。则 auask(fu,k)−ask(p,k)auask(fu,k)−ask(p,k)。第一遍 DFS 求出所有询问并离线下来。第二遍 DFS 求出所有点的 aa。第三遍 DFS 对 aa 做树上前缀和得到所有点的 kk 即可。时间复杂度 O(nlogn)O(nlogn)。Code#include bits/stdc.h#define rept(i,a,b) for(int i(a);ib;i)#define ls(p) ((p)1)#define rs(p) ((p)1|1)#define eb emplace_back#define int long longusing namespace std;constexpr int N5e55;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[N3];void update(int p,int pl,int pr,int pos,int x){ // 单点修改if(plpr) return void(t[p]x);int midplpr1;if(posmid) update(ls(p),pl,mid,pos,x);else update(rs(p),mid1,pr,pos,x);t[p]max(t[ls(p)],t[rs(p)]);}int query(int p,int pl,int pr,int l,int r){ // 区间maxif(lr) return 0;if(lplprr) return t[p];int midplpr1,a0;if(lmid) amax(a,query(ls(p),pl,mid,l,r));if(midr) amax(a,query(rs(p),mid1,pr,l,r));return a;}}sgt;char s[N];int sum[N],dep[N],cnt[N1],a[N],st[N];int n,m,ans;vectorint g[N];vectorQuery q[N];void dfs1(int u){int lstsgt.query(1,1,m,sum[u],sum[u]);sgt.update(1,1,m,sum[u],dep[u]);st[dep[u]]u;for(int v:g[u]){sum[v]sum[u](s[v](?1:-1);dep[v]dep[u]1;if(s[v])){int boundsgt.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);}void dfs2(int u){cnt[sum[u]];for(Query x:q[u]){a[x.id]x.coef*cnt[x.k];}for(int v:g[u]) dfs2(v);--cnt[sum[u]];}void dfs3(int u){for(int v:g[u]){a[v]a[u];dfs3(v);}ans^u*a[u];}signed main(){cin.tie(0)-sync_with_stdio(0);cinns1;mn1;rept(i,2,n){int x;cinx;g[x].eb(i);}g[0].eb(1);sum[0]n,dep[0]1; // 为了不出负数sum统一加上ndfs1(0),dfs2(0),dfs3(0);coutans;return 0;}
给定一棵树，每个节点有一个括号。对于每个节点 ii，定义 sis i 为从根节点到 ii 的路径上所有括号按顺序组成的字符串。求每个 sis i 中互不相同的合
思路首先kiki 可以从父节点递推得到kikfiaikikfiai。其中 aiai 为以节点 ii 结尾的合法括号序列数量。因此只要求出每个节点的 aa。经典技巧将 (( 的权值设为 11)) 设为 −1−1 做树上前缀和。设点 uu 的前缀和为 sumusumu。则以 uu 结尾的合法括号子串的开头 vv 必须满足sumfvsumusumfvsumu。对于 v→uv→u 这条链上的所有点 xx有 sumx≥sumusumx≥sumu。在 DFS 过程中开一棵值域线段树维护 1→u1→u 这条链上每个 sumsum 值对应的最大节点深度。这样就能找到 sumpsumusumpsumu 且深度最大的节点 pp。设 ask(x,y)ask(x,y) 表示 1→x1→x 链上 sumysumy 的节点数量。则 auask(fu,k)−ask(p,k)auask(fu,k)−ask(p,k)。第一遍 DFS 求出所有询问并离线下来。第二遍 DFS 求出所有点的 aa。第三遍 DFS 对 aa 做树上前缀和得到所有点的 kk 即可。时间复杂度 O(nlogn)O(nlogn)。Code#include bits/stdc.h#define rept(i,a,b) for(int i(a);ib;i)#define ls(p) ((p)1)#define rs(p) ((p)1|1)#define eb emplace_back#define int long longusing namespace std;constexpr int N5e55;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[N3];void update(int p,int pl,int pr,int pos,int x){ // 单点修改if(plpr) return void(t[p]x);int midplpr1;if(posmid) update(ls(p),pl,mid,pos,x);else update(rs(p),mid1,pr,pos,x);t[p]max(t[ls(p)],t[rs(p)]);}int query(int p,int pl,int pr,int l,int r){ // 区间maxif(lr) return 0;if(lplprr) return t[p];int midplpr1,a0;if(lmid) amax(a,query(ls(p),pl,mid,l,r));if(midr) amax(a,query(rs(p),mid1,pr,l,r));return a;}}sgt;char s[N];int sum[N],dep[N],cnt[N1],a[N],st[N];int n,m,ans;vectorint g[N];vectorQuery q[N];void dfs1(int u){int lstsgt.query(1,1,m,sum[u],sum[u]);sgt.update(1,1,m,sum[u],dep[u]);st[dep[u]]u;for(int v:g[u]){sum[v]sum[u](s[v](?1:-1);dep[v]dep[u]1;if(s[v])){int boundsgt.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);}void dfs2(int u){cnt[sum[u]];for(Query x:q[u]){a[x.id]x.coef*cnt[x.k];}for(int v:g[u]) dfs2(v);--cnt[sum[u]];}void dfs3(int u){for(int v:g[u]){a[v]a[u];dfs3(v);}ans^u*a[u];}signed main(){cin.tie(0)-sync_with_stdio(0);cinns1;mn1;rept(i,2,n){int x;cinx;g[x].eb(i);}g[0].eb(1);sum[0]n,dep[0]1; // 为了不出负数sum统一加上ndfs1(0),dfs2(0),dfs3(0);coutans;return 0;}
