#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+10; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return xf; } int n,d[N],fa[N],a[N],b[N],k[N],ans; signed main(){ n=read(); for(int i=1;i<=n;i++){ char ch=getchar(); while(ch!='('&&ch!=')') ch=getchar(); if(ch=='(') d[i]=1; else d[i]=-1; } for(int i=2;i<=n;i++) fa[i]=read(); for(int i=1;i<=n;i++){ if(i==1) continue; if(d[i]==1) k[i]=k[fa[i]]; else{ int now=fa[i]; while(d[now]!=1&&now) now=fa[b[now]]; if(now){ a[i]=a[fa[now]]+1; b[i]=now; } k[i]=k[fa[i]]+a[i]; } ans=ans^(ik[i]); } cout<<ans<<endl; return 0; }

注意到每次加入新括号都是在区间尾，并且合法括号序列只有两种： 不可分割合法序列： 不可拆分的合法序列，即左端点与右端点相匹配的合法序列。 组合合法序列： 由多个 连续的 不可拆分合法序列组合而成的合法序列。 于是，如果末尾加入的括号要对合法序列个数的增加有贡献，那么需要满足： 1. 是右括号 2. 左边有等待匹配的左括号 如果满足上述条件，那么这一对括号匹配后就会成为一个 不可分割合法序列 ，剩下的贡献就是考虑这个子序列与其他子序列合并后的贡献了，注意到合并后的新序列一定是一个 连续的 ， 包含末尾 的序列，所以记录每个点向左 连续的 不可分割合法序列有多少个就行了。 这样，当前区间左匹配点之前连续的每一个不可分割合法序列的左端点到末尾就又是一个组合合法序列，由于记录了连续的个数，所以计算贡献是 O(1) 的。 而对于等待匹配的左括号，可以用链表或者栈维护。 同理，不难推广到树上的每条链，复杂度 O(n) 。 如果是栈维护，回溯时还没匹配的记得退栈，这里是链表实现。

#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+10; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return xf; } int n,d[N],fa[N],a[N],b[N],k[N],ans; signed main(){ n=read(); for(int i=1;i<=n;i++){ char ch=getchar(); while(ch!='('&&ch!=')') ch=getchar(); if(ch=='(') d[i]=1; else d[i]=-1; } for(int i=2;i<=n;i++) fa[i]=read(); for(int i=1;i<=n;i++){ if(i==1) continue; if(d[i]==1) k[i]=k[fa[i]]; else{ int now=fa[i]; while(d[now]!=1&&now) now=fa[b[now]]; if(now){ a[i]=a[fa[now]]+1; b[i]=now; } k[i]=k[fa[i]]+a[i]; } ans=ans^(ik[i]); } cout<<ans<<endl; return 0; }

下面的抑或可以先不管他，我们只要O(n)求出每个kik_iki 然后算就是了。 直接求合法串数比较麻烦，我们先固定右端点讨论。 如果右端点是“（”那么答案数是零。 如果是“)”，那么有两种情况， ① (A) ② A1 A2 ...... (An) 考虑用经典的栈来存左括号然后一个一个消，那么某个右括号所匹配的左括号一定是最短的合法串的左端点了，然后如果这个串还要更长的话，此左括号的左边一定是紧接着的另一个合法串。 令dp[i]为以i为右端点的合法串数， 设j为i是右括号情况下匹配的左括号的结点编号， 则 所以当前结点的总方案数ans[i]就等于ans[fi]+dp[i]^{ans[f_i]}+dp[i]ans[fi ]+dp[i] AC代码 欢迎加入团队

giegie~

#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+10; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }return xf; } int n,d[N],fa[N],a[N],b[N],k[N],ans; signed main(){ n=read(); for(int i=1;i<=n;i++){ char ch=getchar(); while(ch!='('&&ch!=')') ch=getchar(); if(ch=='(') d[i]=1; else d[i]=-1; }for(int i=2;i<=n;i++) fa[i]=read(); for(int i=1;i<=n;i++){ if(i==1) continue; if(d[i]==1) k[i]=k[fa[i]]; else{ int now=fa[i]; while(d[now]!=1&&now) now=fa[b[now]]; if(now){ a[i]=a[fa[now]]+1; b[i]=now; }k[i]=k[fa[i]]+a[i]; }ans=ans^(ik[i]); }cout<<ans<<endl; return 0; }