以后考试前一定要擦一下眼镜…
题很简单,不看错就行,考场看错题,还以为是样例错了QAQ
如果 A,B 是合法括号串,则 AB 是合法括号串。
考试是没注意这一点,一直以为()(->()(),只会增加一个合法括号,结果有2,然后爆掉.
因为是要爆栈的,所以把dfs换成bfs就可以了。
用冰茶姬来判断匹配的左括号,每匹配一个就往前找下一个有括号能够匹配的。
如下
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+1;
int n;
int tot;
char s[N];
int head[N];
int pre[N],dp[N],top[N];
struct Kano{
int u,v;
}kano[2*N];
inline void add(int x,int y){
kano[++tot].u=head[x];
kano[tot].v=y;
head[x]=tot;
return ;
}
inline void bfs(){
queue<int>boy;
boy.push(1);
while(!boy.empty()){
int now=boy.front();
boy.pop();
if(s[now]=='('){
top[now]=now;
}else{
int x=top[pre[now]];
if(x){
dp[now]=dp[pre[x]]+1;//每次不是只加1个,是从一个大的括号加.
}
top[now]=top[pre[x]];
}
for(int i=head[now];i;i=kano[i].u){
int v=kano[i].v;
boy.push(v);
}
}
}
inline void bfs2(){
queue<int>boy;
boy.push(1);
while(!boy.empty()){
int now=boy.front();
boy.pop();
for(int i=head[now];i;i=kano[i].u){
int v=kano[i].v;
dp[v]+=dp[now];
boy.push(v);
}
}
}
signed main(){
scanf("%lld",&n);
scanf("%s",s+1);
for(int i=2;i<=n;++i){
scanf("%lld",&pre[i]);
add(pre[i],i);
}
bfs();
bfs2();
int res=0;
for(int i=1;i<=n;++i){
res^=(i*dp[i]);
}
printf("%lld",res);
return 0;
}
考试惨案