rt,原来过了样例,一通乱改过不了样例了。但一直是 34pts。
#include<bits/stdc++.h>
using namespace std;
const int N = 40005;
int n;
vector<int> e[N];
char kh[N];
bool vis[N];
int mxzs[N], jds[N];
queue<int> q;
int mx_pre[N], mx_suf[N], zhan[N], bowl[N], ans;
void find_zx(int u, int fa){
q.push(u);
jds[u] = 1, mxzs[u] = 0;
int L = e[u].size();
for(int i = 0; i < L; ++i){
int v = e[u][i];
if(vis[v] || v == fa) continue;
find_zx(v, u);
jds[u] += jds[v], mxzs[u] = max(mxzs[u], jds[v]);
}
return ;
}
void find_pre(int u, int fa){
if(kh[u] == '('){
zhan[u] = zhan[fa] - 1;
mx_pre[u] = mx_pre[fa];
//mx_pre[u] = max(mx_pre[fa], zhan[u]);
}
else{
zhan[u] = zhan[fa] + 1;
mx_pre[u] = max(mx_pre[fa], zhan[u]);
if(zhan[u] >= 0)
ans = max(ans, max(mx_pre[u], bowl[zhan[u]]));
}
int L = e[u].size();
for(int i = 0; i < L; ++i){
int v = e[u][i];
if(fa == v || vis[v]) continue;
find_pre(v, u);
}
zhan[u] = 0, mx_pre[u] = 0;
return ;
}
void find_suf(int u, int fa){
if(kh[u] == ')'){
//cout << "2! ";
zhan[u] = zhan[fa] - 1;
mx_suf[u] = mx_suf[fa];
}
else{
//cout << "1! ";
zhan[u] = zhan[fa] + 1;
mx_suf[u] = max(zhan[u], mx_suf[fa]);
if(zhan[u] >= 0) bowl[zhan[u]] = max(bowl[zhan[u]], mx_suf[u]);
}
int L = e[u].size();
for(int i = 0; i < L; ++i){
int v = e[u][i];
if(fa == v || vis[v]) continue;
find_suf(v, u);
}
mx_suf[u] = 0;
zhan[u] = 0;
return ;
}
void dfz(int root){
find_zx(root, 0);
int all = jds[root];
while(!q.empty()){
int u = q.front();
q.pop();
mxzs[u] = max(mxzs[u], all - jds[u]);
if(mxzs[u] < mxzs[root]) root = u;
}
//printf("%d", root);
int L = e[root].size();
//cout << L << endl;
if(kh[root] == '(') bowl[1] = 1;
for(int i = 0; i < L; ++i){
int v = e[root][i];
if(vis[v]) continue;
zhan[root] = 0, mx_suf[root] = 0;
find_pre(v, root);
if(kh[root] == '(') zhan[root] = -1;
else zhan[root] = 1, mx_suf[root] = 1;
find_suf(v, root);
}
zhan[root] = 0;mx_suf[root] = 0;
memset(bowl, 0, sizeof bowl);
vis[root] = 1;
L = e[root].size();
for(int i = 0; i < L; ++i){
int v = e[root][i];
if(!vis[v]) dfz(v);
}
return ;
}
int main(){
scanf("%d", &n);
for(int u = 2; u <= n; ++u){
int v;
scanf("%d", &v);
e[u].push_back(v), e[v].push_back(u);
}
for(int i = 1; i <= n; ++i){
cin >> kh[i];
}
dfz(1);
printf("%d", ans);
return 0;
}