This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define DEBUG false
vector<vector<int> > g;
string s;
int n;
vector<int> alive;
int ans = 0;
vector<int> sz;
void dfs1(int cur, int par){
if(DEBUG) cout<<"INSIDE "<<cur<<endl;
sz[cur] = 1;
for(int u: g[cur]){
if(u == par || alive[u] == false) continue;
dfs1(u, cur);
sz[cur] += sz[u];
}
}
int find(int cur, int par, int size){
int big = -1;
for(int u: g[cur]){
if(u == par || alive[u] == false) continue;
if(big == -1 || sz[u] > sz[big]){
big = u;
}
}
if(big == -1 || sz[big]*2 <= size) return cur;
else return find(big, cur, size);
}
vector<int> f;
vector<vector<int> > subf;
int off = 0;
void dfs2(int cur, int par, int val, int low, int part){
val += s[cur] == '('?1:-1;
low = min(low, val);
if(low == val){
f[val + off]++;
subf[part][val + subf[part].size()/2]++;
}
for(int u: g[cur]){
if(u == par || alive[u] == false) continue;
dfs2(u, cur, val, low, part);
}
}
void dfs3(int cur, int par, int val, int low, int part){
val += s[cur] == '('?1:-1;
low = min(low+val, s[cur]=='('?1LL:-1LL);
if(low >= 0){
ans += f[-val + off] - subf[part][-val + subf[part].size()/2];
if(DEBUG)cout<<"INC ANS "<<cur<<" "<<f[-val + off] - subf[part][-val + subf[part].size()/2]<<endl;
}
for(int u: g[cur]){
if(u == par || alive[u] == false) continue;
dfs3(u, cur, val, low, part);
}
}
void decomp(int cur){
if(DEBUG)cout<<"CUR : "<<cur<<endl;
dfs1(cur, -1);
int cent = find(cur, -1, sz[cur]);
if(DEBUG)cout<<"CENT "<<cent<<endl;
f = vector<int>(sz[cent]*2+1, 0);
off = sz[cent];
// cout<<"SZ: "<<g[cent].size()<<" "<<subf.size()<<endl;
int val = s[cent] == '('?1:-1;
f[val + off]++;
for(int i = 0; i < g[cent].size(); i++){
if(!alive[g[cent][i]]) continue;
subf[i] = vector<int>(sz[g[cent][i]]*2+10, 0);
dfs2(g[cent][i], cent, val, min(val, 0LL), i);
}
for(int i = 0; i < g[cent].size(); i++){
if(!alive[g[cent][i]]) continue;
dfs3(g[cent][i], cent, 0, 0, i);
}
ans += f[0 + off];
alive[cent] = false;
for(int u: g[cent]){
if(alive[u]) decomp(u);
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
cin>>s;
g.resize(n);
for(int i = 0; i < n-1; i++){
int u, v; cin>>u>>v; u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
alive = vector<int>(n, true);
ans = 0;
sz = vector<int>(n, 0);
subf = vector<vector<int> > (2*n);
decomp(0);
cout<<ans<<endl;
}
Compilation message (stderr)
zagrade.cpp: In function 'void decomp(long long int)':
zagrade.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[cent].size(); i++){
~~^~~~~~~~~~~~~~~~
zagrade.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[cent].size(); i++){
~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |