WA34pts求调
查看原帖
WA34pts求调
683859
complete_binary_tree楼主2024/2/26 19:29

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;
}
2024/2/26 19:29
加载中...