本人的第二篇题解

考虑[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)

/*
以免有人超题解（别抄！）就不写头文件
*/

#define MAXN 500011
struct Edge
{
	ll v,nxt;
}e[MAXN];
ll cnt=0,last[MAXN];
void adde(ll u,ll v)
{
	e[++cnt].v=v;
	e[cnt].nxt=last[u],last[u]=cnt;
}
char a[MAXN];
ll fa[MAXN],s[MAXN],f[MAXN];//父亲,栈,f如上所述
ll ans=0;
void dfs(ll u,ll pre,ll top)//当前点为u,1到父亲的合法子串数为pre,当前栈顶指针
{
	ll flag=0;//用于处理上述特殊情况
	if(a[u]=='(')//分类讨论
	{
		s[++top]=u;
	}
	else
	{
		if(!top)f[u]=0;
		else
		{
			flag=s[top];//存下栈顶
			f[u]=f[fa[s[top]]]+1;//更新f
			pre+=f[u];//更新pre
			--top;//pop
		}
		
	}
	//printf("vis %lld,f=%lld\n",u,pre);
	ans^=(u*pre);//统计贡献
	for(ll i=last[u];i;i=e[i].nxt)
		dfs(e[i].v,pre,top);
	if(flag)s[top+1]=flag;//恢复栈顶
}
int main()
{
	ll n=read();
	scanf("%s",a+1);
	for(ll i=2;i<=n;++i)
	{
		fa[i]=read();
		adde(fa[i],i);
	}
	dfs(1,0,0);
	printf("%lld",ans);
	return 0;
}

欢迎加入团队！！！！（快来吧缺人）