zcmimi's blog

查看原题

点击跳转

在dfs的过程中维护一个栈st

假设当前遍历节点为x,栈顶st[tp]

x与栈顶形成一个括号对,那么弹出栈顶,将新的栈顶权值+1

栈顶权值表示:

如果有新的右括号入栈,以这个右括号结尾,能形成多少合法括号串

#include<bits/stdc++.h>
const int N=500011;
int n,cnt,head[N],f[N];
char c[N];
struct edge{int to,nxt;}e[N];
void add(int x,int y){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt;}
long long ans=0,s[N],ps[N];
int st[N],tp,v[N];
void dfs(int x){
    s[x]=s[f[x]];
    int ff=0;
    if(c[st[tp]]=='('&&c[x]==')')
        ff=st[tp],s[x]+=++v[st[--tp]];
    else st[++tp]=x;
    for(int i=head[x];i;i=e[i].nxt)dfs(e[i].to);
    // 回溯
    if(ff)--v[st[tp]],st[++tp]=ff;
    else --tp;
}
int main(){
    scanf("%d%s",&n,c+1);
    for(int i=2;i<=n;++i)
        scanf("%d",f+i),add(f[i],i);
    dfs(1);
    for(int i=1;i<=n;++i)ans^=i*s[i];
    printf("%lld\n",ans);
}
LG 5658 括号树
comment评论
Search
search