考虑[1,u]的合法子串数=[1,fa[u]]的合法子串数+加入u后新增的合法子串数. 前面这个,直接在dfs的时候向下传递就好了.后面这部分呢? 分类讨论,并维护一个栈,存未被匹配的左括号的编号. 数组f[u]表示以u结尾的新增的合法子串数 1、当前点的字符为(:新增的合法子串数为0,直接进栈. 2、当前点字符为),但栈为空,新增的合法子串数也是0. 3、当前点字符为),且栈非空,更新f[u]=f[fa[s[top]]]+1(这句话的含义是,到u的新增合法子串,要么是由栈顶父亲那里的合法串加上[s[top],u]这一对括号构成的,要么就是[s[top],u]这一对括号),并pop掉栈顶. PS:我的实现全局只用一个栈,而u在dfs完某部分子树后,栈内部分元素可能被这部分子树内的(所覆盖,导致dfs完后,现在的栈存的不再是[1,u]中未被匹配的(编号了.这个问题有很多种解决办法,我的解决方案是:如果当前的u触发了退栈操作,存一下当前的栈顶,再pop,dfs完所有子树后,恢复栈顶. 时间复杂度显然是线性的,即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; }

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

题意分析 给定一颗树，每个节点上有一个左或右括号，设1到iii节点的简单路径中有cnticnt_icnti 个子串为合法括号子串，求出所有cnti×icnt_i \times icnti ×i的异或和。 具体思路 参考普通括号序列计数dpdpdp，括号序列的状态可以分为两种，一种是不可分割为两个合法序列的，即（A），一种是可以分割为两个合法序列的，即AB。 定义dpidp_idpi 为到节点iii为止，路径上所有不同合法子串的总数（即所有位置结尾的合法子串数量之和），cnticnt_icnti 为以节点iii结尾的连续不可分割的合法序列个数。 对于每个节点iii，其父节点为fff： 如果是左括号，则无法为合法字串数量做出贡献，将iii放入栈中准备匹配。 如果是右括号，则检测栈中是否有等待匹配的左括号，如果栈顶有左括号节点jjj，则弹出jjj，使cnti=cntj+1cnt_i = cnt_j+1cnti =cntj +1，dpi=cnti+dpfdp_i=cnt_i+dp_fdpi =cnti +dpf 。 否则，无法做出贡献，因为是右节点，所以也无法放入栈中匹配。 回溯是很重要的一步，如果不进行回溯，父节点进行其他路径的搜索时栈中会仍有上条路径还未匹配的左括号节点，搜索时也可能因为父节点作为左括号在上条路径中被匹配导致栈中没有父节点，从而使得右括号匹配不上，计算结果变小。 AC代码 时间复杂度 O(n)O(n)O(n)，跑一遍dfsdfsdfs就出结果了，但似乎常数因子较大，还有待优化。

#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; }