题目描述
NOIP day1t2
分析
1.考虑状态,只需要知道以当前的括号为边能够产生的合法答案再递推就可以了。
2.状态转移,思考清楚,左括号对左括号,右括号对右括号,(考试少递推个父亲就一句90没了)。
C++ 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,t,f[N],w[N],net[N];
ll ans[N],tot[N];
struct mn{
int to,nex;
}s[N];
void add(int a,int b){
s[++t].to=b;
s[t].nex=net[a];
net[a]=t;
}
void dfs(int x,int ff){
if(ff){
if(w[x]){
if(w[ff])
f[x]=ff;
else{
tot[x]=tot[ff];
f[x]=f[ff];//命案发生点
}
}
else{
if(w[ff]){
f[x]=f[ff];
tot[x]=tot[ff]+1;
}
else{
if(f[ff]){
tot[x]=1+tot[f[ff]];
f[x]=f[f[ff]];
}
}
}
}
for(int i=net[x];i;i=s[i].nex)
dfs(s[i].to,x);
}
void dfss(int x,int ff){
ans[x]+=ans[ff];
if(w[x]==0)
ans[x]+=tot[x];
for(int i=net[x];i;i=s[i].nex)
dfss(s[i].to,x);
}
int main()
{
cin>>n;
char c;
int a;
for(int i=1;i<=n;i++){
scanf(" %c",&c);
if(c=='(')
w[i]=1;
}
for (int i=2;i<=n;i++){
scanf("%d",&a);
add(a,i);
}
dfs(1,0);
dfss(1,0);
ll anss=ans[1];
for(ll i=2;i<=n;i++)
anss^=ans[i]*i;
cout<<anss;
return 0;
}