#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int N = 300100;
vector<int> g[N];
ll ans;
int n, siz[N], ad[N], sta[N], ed[N], mn_sta[N], mn_ed[N], mem[N];
bool used[N];
string s;
void build_sz(int v, int p){
siz[v] = 1;
for (int u : g[v]){
if (u == p || used[v]) continue;
build_sz(u, v);
siz[v] += siz[u];
}
}
int search(int v, int pr, int SZ){
for (int u : g[v]){
if (u == pr || used[v]) continue;
if (siz[u] > SZ / 2)
return search(u, v, SZ);
}
return v;
}
void dfs(int v, int pr){
mn_sta[v] = min(mn_sta[pr] + ad[v], 0);
mn_ed[v] = min(mn_ed[pr] - ad[v], 0);
sta[v] = sta[pr] + ad[v];
ed[v] = ed[pr] + ad[v];
for (int u : g[v]){
if (used[u] || u == pr) continue;
dfs(u, v);
}
}
void calc(int v, int pr){
if (mn_sta[v] == 0)
ans += mem[sta[v]];
for (int u : g[v]){
if (used[u] || u == pr) continue;
calc(u, v);
}
}
void upda(int v, int pr){
if (mn_ed[v] == 0)
mem[-ed[v]]++;
for (int u : g[v]){
if (used[u] || u == pr) continue;
upda(u, v);
}
}
void build_cd(int v){
build_sz(v, -1);
int SZ = siz[v];
int cen = search(v, -1, siz[v]);
used[cen] = 1;
// calc subtree sums
sta[cen] = 0;
ed[cen] = ad[cen];
mn_ed[cen] = min(0, -ad[cen]);
mn_sta[cen] = 0;
for (int it = 0; it < sz(g[v]); it++)
int u = g[v][it];
if (used[u]) {
swap(g[v].back(), g[v][it]);
g[v].pop_back();
it--;
continue;
}
dfs(u, cen);
}
// update ans (left, right)
//left
fill(mem, mem + SZ + 1, 0);
if (mn_ed[cen] == 0)
mem[-ed[cen]]++;
for (int u : g[cen]){
if (used[u]) continue;
calc(u, cen);
upda(u, cen);
}
//right
fill(mem, mem + SZ + 1, 0);
reverse(all(g[cen]));
for (int u : g[cen]){
if (used[u]) continue;
calc(u, cen);
upda(u, cen);
}
if (mn_sta[cen] == 0)
ans += mem[sta[cen]];
// continue process in children subtrees
for (int u : g[cen])
if (!used[u])
build_cd(u);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> s;
for (int i = 0; i < n; i++){
if (s[i] == '(')
ad[i] = 1;
else ad[i] = -1;
}
for (int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
}
build_cd(0);
cout << ans;
return 0;
}
Compilation message
zagrade.cpp: In function 'void build_cd(int)':
zagrade.cpp:93:27: error: 'sz' was not declared in this scope
for (int it = 0; it < sz(g[v]); it++)
^~
zagrade.cpp:93:27: note: suggested alternative: 's'
for (int it = 0; it < sz(g[v]); it++)
^~
s
zagrade.cpp:93:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int it = 0; it < sz(g[v]); it++)
^~~
zagrade.cpp:96:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
if (used[u]) {
^~
zagrade.cpp:94:13: warning: unused variable 'u' [-Wunused-variable]
int u = g[v][it];
^
zagrade.cpp:96:18: error: 'u' was not declared in this scope
if (used[u]) {
^
zagrade.cpp:97:36: error: 'it' was not declared in this scope
swap(g[v].back(), g[v][it]);
^~
zagrade.cpp:97:36: note: suggested alternative: 'int'
swap(g[v].back(), g[v][it]);
^~
int
zagrade.cpp:100:13: error: continue statement not within a loop
continue;
^~~~~~~~
zagrade.cpp:103:13: error: 'u' was not declared in this scope
dfs(u, cen);
^
zagrade.cpp:80:9: warning: unused variable 'SZ' [-Wunused-variable]
int SZ = siz[v];
^~
zagrade.cpp: At global scope:
zagrade.cpp:110:9: error: expected constructor, destructor, or type conversion before '(' token
fill(mem, mem + SZ + 1, 0);
^
zagrade.cpp:112:5: error: expected unqualified-id before 'if'
if (mn_ed[cen] == 0)
^~
zagrade.cpp:115:5: error: expected unqualified-id before 'for'
for (int u : g[cen]){
^~~
zagrade.cpp:124:9: error: expected constructor, destructor, or type conversion before '(' token
fill(mem, mem + SZ + 1, 0);
^
zagrade.cpp:126:12: error: expected constructor, destructor, or type conversion before '(' token
reverse(all(g[cen]));
^
zagrade.cpp:128:5: error: expected unqualified-id before 'for'
for (int u : g[cen]){
^~~
zagrade.cpp:135:5: error: expected unqualified-id before 'if'
if (mn_sta[cen] == 0)
^~
zagrade.cpp:140:5: error: expected unqualified-id before 'for'
for (int u : g[cen])
^~~
zagrade.cpp:143:1: error: expected declaration before '}' token
}
^
