本人的第二篇题解
2026-02-10 21:30:34
发布于:广东
5阅读
0回复
0点赞
考虑[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;
}
全部评论 2
又发题解了
1周前 来自 广东
0666

1周前 来自 广东
0








有帮助,赞一个