#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 3e5+5, mod = 1e9+7, K = 20;
int n;
vector<int>gr[N];
int sz[N],fix[N],A[N][2];
int answer;
char c;
void dfs(int x,int p){
sz[x] = 1;
for(auto to : gr[x]){
if(to == p || fix[to]) continue;
dfs(to,x);
sz[x] += sz[to];
}
}
int get_centroid(int x,int p,int total){
int mx = total - sz[x];
int ind = 0;
for(auto to : gr[x]){
if(to == p || fix[to]) continue;
if(mx < sz[to]){
mx = sz[to];
ind = to;
}
}
if(mx*2 <= total){
return x;
}
return get_centroid(ind,x,total);
}
void get(int x,int p,int k,int cur,vector<int>&cnt,int mx){
cur += A[x][k];
if(mx <= cur){
cnt[cur]++;
}
mx = max(mx,A[x][k]);
for(auto to : gr[x]){
if(to == p || fix[to]) continue;
get(to,x,k,cur,cnt,mx);
}
}
void get1(int x,int p,int k,int cur){
cur += A[x][k];
if(cur == 0)answer++;
if(cur < 0) return ;
for(auto to : gr[x]){
if(to == p || fix[to]) continue;
get1(to,x,k,cur);
}
}
void go(int x,int total){
if(total == 1) return ;
dfs(x,0);
int centroid = get_centroid(x,0,total);
dfs(centroid,0);
vector<vector<int>>cnt(2,vector<int>(total+5,0));
int cur0 = 0,cur1 = 0;
for(auto to : gr[centroid]){
if(fix[to]) continue;
vector<vector<int>>cur_cnt(2,vector<int>(sz[to]+5,0));
get(to,centroid,0,0,cur_cnt[0],0);
get(to,centroid,1,0,cur_cnt[1],0);
for(int k = 0; k <= 1; k++){
for(int i = 0; i <= sz[to]+1; i++){
if(cur_cnt[k][i] == 0) continue;
answer += cur_cnt[k][i]*cnt[1-k][i];
//cout << cur_cnt[k][i]*cnt[1-k][i] << endl;
}
//answer += cur_cnt[k][0]*(cnt[0][0]+cnt[1][0]);
//cout << to << " " << k << endl;
//cout << cur_cnt[k][0]*(cnt[0][0]+cnt[1][0]) << " 0000" << endl;
}
for(int k = 0; k <= 1; k++){
for(int i = 0; i <= sz[to]+1; i++){
if(i+A[centroid][k] >= 0)
cnt[k][i+A[centroid][k]] += cur_cnt[k][i];
}
}
}
//cout << centroid << " " << answer << endl;
answer += cnt[0][0] + cnt[1][0];
fix[centroid] = 1;
for(auto to : gr[centroid]){
if(fix[to] == 1) continue;
go(to,sz[to]);
}
}
int main(){
freopen("a.txt","r",stdin);
ios::sync_with_stdio(0);
cin >> n;
//cout << n << endl;
for(int i = 1; i <= n; i++){
cin >> c;
if(c == '(') A[i][0] = 1, A[i][1] = -1;
if(c == ')') A[i][0] = -1, A[i][1] = 1;
}
for(int i = 1; i < n; i++){
int x,y;
cin >> x >> y;
gr[x].pb(y);
gr[y].pb(x);
}
go(1,n);
cout << answer << endl;
}
Compilation message
zagrade.cpp: In function 'void go(int, int)':
zagrade.cpp:87:9: warning: unused variable 'cur0' [-Wunused-variable]
87 | int cur0 = 0,cur1 = 0;
| ^~~~
zagrade.cpp:87:18: warning: unused variable 'cur1' [-Wunused-variable]
87 | int cur0 = 0,cur1 = 0;
| ^~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | freopen("a.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
