#include <bits/stdc++.h>
using namespace std;
typedef long long llint;
const int maxn = 3e5+10;
int n;
int niz[maxn];
vector< int > graph[maxn];
bool bio[maxn];
int cnt[maxn];
pair<int, int> fin(int x, int parr, int siz) {
bool flag = true;
int ac = 1;
int cen = -1;
int suma = siz - 1;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren == parr) continue;
if (bio[tren]) continue;
pair<int, int> t = fin(tren, x, siz);
ac += t.second;
suma -= t.second;
if (t.second > siz / 2) flag = false;
cen = max(cen, t.first);
}
if (flag && suma <= siz / 2) cen = x;
return make_pair(cen, ac);
}
int cn(int x, int parr) {
int out = 1;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (bio[tren]) continue;
if (tren == parr) continue;
out += cn(tren, x);
}
return out;
}
llint las(int x, int parr, int sum, int mini) {
llint out = 0;
sum += niz[x];
mini = min(mini, sum);
if (sum <= mini && sum <= 0) out += cnt[-sum];
//printf("las %d %d %d %d\n", x, parr, sum, mini);
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren == parr) continue;
if (bio[tren]) continue;
out += las(tren, x, sum, mini);
}
return out;
}
void fron(int x, int parr, int sum, int mini) {
sum += niz[x];
mini = min(niz[x], mini + niz[x]);
if (mini >= 0) cnt[sum]++;
//printf("fron %d %d %d %d\n", x, parr, sum, mini);
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren == parr) continue;
if (bio[tren]) continue;
//printf("conn: %d %d\n", x, tren);
fron(tren, x, sum, mini);
}
//printf("ret fron %d %d\n", x, parr);
}
llint f(int x, int siz) {
//printf("fin %d %d\n", x, siz);
int cen = fin(x, -1, siz).first;
llint out = 0;
//printf("fin start cal (cen = %d)\n", cen);
memset(cnt, 0, sizeof cnt);
//if (niz[cen] == 1) cnt[1] = 1;
cnt[0]++;
for (int i = 0; i < graph[cen].size(); i++) {
int tren = graph[cen][i];
if (bio[tren]) continue;
out += las(tren, cen, niz[cen], niz[cen]);
fron(tren, cen, 0, 0);
}
if (niz[cen] == -1) out += cnt[1];
memset(cnt, 0, sizeof cnt);
for (int i = graph[cen].size() - 1; i >= 0; i--) {
int tren = graph[cen][i];
if (bio[tren]) continue;
out += las(tren, cen, niz[cen], niz[cen]);
fron(tren, cen, 0, 0);
}
bio[cen] = true;
for (int i = 0; i < graph[cen].size(); i++) {
int tren = graph[cen][i];
if (bio[tren]) continue;
int si = cn(tren, -1);
out += f(tren, si);
}
return out;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
char c;
scanf(" %c", &c);
if (c == '(') niz[i] = 1;
else niz[i] = -1;
}
for (int i = 1; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
memset(bio, false, sizeof bio);
printf("%lld\n", f(1, n));
return 0;
}
Compilation message
zagrade.cpp: In function 'std::pair<int, int> fin(int, int, int)':
zagrade.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int cn(int, int)':
zagrade.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint las(int, int, int, int)':
zagrade.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'void fron(int, int, int, int)':
zagrade.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint f(int, int)':
zagrade.cpp:90:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[cen].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[cen].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
zagrade.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &c);
~~~~~^~~~~~~~~~~
zagrade.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 2 |
Correct |
80 ms |
8832 KB |
Output is correct |
| 3 |
Correct |
79 ms |
8952 KB |
Output is correct |
| 4 |
Correct |
79 ms |
8832 KB |
Output is correct |
| 5 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 6 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8952 KB |
Output is correct |
| 8 |
Correct |
80 ms |
8952 KB |
Output is correct |
| 9 |
Correct |
77 ms |
8704 KB |
Output is correct |
| 10 |
Correct |
76 ms |
8960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
43172 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 2 |
Correct |
80 ms |
8832 KB |
Output is correct |
| 3 |
Correct |
79 ms |
8952 KB |
Output is correct |
| 4 |
Correct |
79 ms |
8832 KB |
Output is correct |
| 5 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 6 |
Correct |
77 ms |
8832 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8952 KB |
Output is correct |
| 8 |
Correct |
80 ms |
8952 KB |
Output is correct |
| 9 |
Correct |
77 ms |
8704 KB |
Output is correct |
| 10 |
Correct |
76 ms |
8960 KB |
Output is correct |
| 11 |
Execution timed out |
3070 ms |
43172 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
