#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
typedef long double Real;
const int MOD = 2004010501; //MOD > 2e9
const int N = 3e5 + 5;
int num_nodes; char ch[N];
vector<int> tree[N];
bool done[N];
int siz[N];
void calc_siz(int u, int pa) {
siz[u] = 1;
for (auto v : tree[u])
if (!done[v] and v != pa) calc_siz(v,u), siz[u] += siz[v];
}
int centroid(int u, int pa, int total) {
for (auto v : tree[u])
if (!done[v] and v != pa and 2*siz[v] > total)
return centroid(v,u,total);
return u;
}
/*
tiền tố A, hậu tố B
. O(a,i) - C(a,i) >= 0
. C(b,i) - O(b,i) >= 0
. O(a)-C(a) + O(b)-C(b) = 0
delta(a) = -delta(b)
-N <= delta <= N
khi dfs xuống, duy trì min
*/
const int MIN = -N;
const int MAX = +N;
int freq_pref[MAX-MIN+1];
int freq_suff[MAX-MIN+1];
#define fre_p(x) freq_pref[x-MIN]
#define fre_s(x) freq_suff[x-MIN]
struct Info {
int s1,m1,s2,m2;
Info() { s1 = s2 = m1 = m2 = 0; }
void add(char p) {
int d = (p == '(') ? +1 : -1;
m1 = min(s1+=d, m1+d);
m2 = min(s2-=d, m2-d);
}
};
void dfs_update(int u, int pa, Info val, int add) {
val.add(ch[u]);
if (val.m1 >= 0) fre_p(val.s1) += add;
if (val.m2 >= 0) fre_s(val.s2) += add;
for (auto v : tree[u]) if (!done[v] and v != pa)
dfs_update(v,u,val,add);
}
Int answer = 0;
void dfs_query(int u, int pa, Info val) {
val.add(ch[u]);
if (val.m1 >= 0) answer += fre_s(val.s1);
if (val.m2 >= 0) answer += fre_p(val.s2);
for (auto v : tree[u]) if (!done[v] and v != pa)
dfs_query(v,u,val);
}
void centroid_decompose(int u) {
calc_siz(u,-1);
int g = centroid(u, -1, siz[u]);
done[g] = true;
Info root; root.add(ch[g]);
if (root.m1 >= 0) ++fre_p(root.s1);
if (root.m2 >= 0) ++fre_s(root.s2);
for (auto v : tree[g]) {
dfs_query(v,g, Info());
dfs_update(v,g, root, +1);
}
if (root.m1 >= 0) --fre_p(root.s1);
if (root.m2 >= 0) --fre_s(root.s2);
for (auto v : tree[g])
dfs_update(v,g, root, -1);
for (auto v : tree[g])
centroid_decompose(v);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> num_nodes;
for (int i = 1; i <= num_nodes; i++) cin >> ch[i];
for (int u,v, i = 1; i < num_nodes; i++) {
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
centroid_decompose(1);
cout << answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3090 ms |
14436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1349 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3090 ms |
14436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
