不难发现:
$sum[x]=sum[fa[x]]$+以$x$为结尾的合法数量
初想发现有点困难。
但貌似仔细想想之后,
$)$只能匹配一个$($
也就是说,一定在某个位置进行了累加(也就是"$AB$")
那么以$x$为结尾的合法数量可以视作为$1+$前面某一个位置为结尾的合法数量。
前面某一个位置为结尾的合法数量可以通过继承来获取。
维护继承可以用栈,因为只有栈顶的$($能用。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=5e5+5;
int sta[N],top,fa[N];ll sq[N],sum[N];
char s[N];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs(int x)
{
for(int k=last[x],y;k;k=a[k].next)
{
fa[y=a[k].y]=x;
if(s[y]=='(')
{
sum[y]=sum[x];
sta[++top]=y;
dfs(y);
--top;
}
else
{
if(top==0){sum[y]=sum[x];dfs(y);}
else
{
int lst=sta[top--];
sq[y]=sq[fa[lst]]+1;
sum[y]=sum[x]+sq[y];
dfs(y);
sta[++top]=lst;
}
}
}
}
int main()
{
len=0;memset(last,0,sizeof(last));
int n;scanf("%d",&n);
scanf("%s",s+1);top=0;
for(int i=2,y;i<=n;i++)scanf("%d",&y),ins(y,i);
sum[1]=0;if(s[1]=='(')sta[++top]=1;dfs(1);
ull ans=0;
for(int i=1;i<=n;i++)
ans^=i*sum[i];
printf("%llu\n",ans);
return 0;
}
最后一次更新于2020-05-13
0 条评论