#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 5;
int n, a[N], sz[N], cnt[N];
bool del[N];
vector<int> g[N];
ll ans;
int dfs_size(int u, int p = 0) {
sz[u] = 1;
for(int v : g[u]) if(v != p && !del[v]) sz[u] += dfs_size(v, u);
return sz[u];
}
int find_centroid(int u, int p, int num) {
for(int v : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
return u;
}
void dfs_open(int u, int p = 0, int val = 0, int num_close = 0) {
num_close = max(num_close, 0);
if(a[u] == -1) ++num_close;
else --num_close;
val += a[u];
if(num_close <= 0) {
ans += cnt[val];
}
for(int v : g[u]) if(v != p && !del[v]) {
dfs_open(v, u, val, num_close);
}
}
void dfs_close(int add, int u, int p = 0, int val = 0, int num_open = 0) {
num_open = max(num_open, 0);
if(a[u] == 1) {
++num_open;
--val;
}
else {
--num_open;
++val;
}
if(num_open <= 0) {
cnt[val] += add;
tmp.push_back(val);
}
for(int v : g[u]) if(v != p && !del[v]) {
dfs_close(add, v, u, val, num_open);
}
}
void decomposition(int u) {
u = find_centroid(u, 0, dfs_size(u));
cen = u;
del[u] = 1;
dfs_close(1, u);
ans += cnt[0];
for(int v : g[u]) if(!del[v]) {
dfs_close(-1, v, u, -a[u], a[u]);
dfs_open(v, u);
dfs_close(1, v, u, -a[u], a[u]);
}
dfs_close(-1, u);
for(int v : g[u]) if(!del[v]) {
decomposition(v);
}
}
void solve() {
cin >> n;
string s; cin >> s;
for(int i = 0; i < s.size(); ++i) {
a[i + 1] = s[i] == '(' ? 1 : -1;
}
for(int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
decomposition(1);
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) solve();
return 0;
}
// https://oj.uz/problem/view/COI17_zagrade
Compilation message
zagrade.cpp: In function 'void dfs_close(int, int, int, int, int)':
zagrade.cpp:47:9: error: 'tmp' was not declared in this scope; did you mean 'tm'?
47 | tmp.push_back(val);
| ^~~
| tm
zagrade.cpp: In function 'void decomposition(int)':
zagrade.cpp:56:5: error: 'cen' was not declared in this scope
56 | cen = u;
| ^~~
zagrade.cpp: In function 'void solve()':
zagrade.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
