#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 3e5 + 15, LOG = 20;
ll n, ans;
string s;
int deep[N], up[N], ok[N], OK[N];
bool neg[N];
int ind[N], T;
int par[LOG][N];
vector <int> G[N], GP[N];
vector <int> ver[N];
int dp[N], ls[N];
void calc (int v = 0, int p = 0) {
par[0][v] = p;
for (int i = 1; i < LOG; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
ind[T++] = v;
deep[v] = 1 + deep[p];
up[v] = up[p] + (s[v] == '('? +1: -1);
ok[v] = v;
if (s[v] == '(') {
int u = ok[p];
if (u != p && u != par[0][u])
u = par[0][u];
if (u != par[0][u] && s[par[0][u]] == '(')
u = ok[par[0][u]];
ok[v] = u;
}
OK[v] = v;
if (s[v] == ')') {
int u = OK[p];
if (u != p && u != par[0][u])
u = par[0][u];
if (u != par[0][u] && s[par[0][u]] == ')')
u = OK[par[0][u]];
OK[v] = u;
}
for (int u: G[v])
if (u != p)
calc(u, v);
}
int lca (int v, int u) {
if (deep[v] < deep[u])
swap(v, u);
int dis = deep[v] - deep[u];
for (int i = 0; i < LOG; i++)
if ((dis >> i) & 1)
v = par[i][v];
if (v == u)
return v;
for (int i = LOG - 1; ~i; i--)
if (par[i][v] != par[i][u]) {
v = par[i][v];
u = par[i][u];
}
return par[0][v];
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n - 1; i++) {
int v, u;
cin >> v >> u;
v--, u--;
G[v].push_back(u);
G[u].push_back(v);
}
if (n <= -1000) {
calc();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j)
continue;
int k = lca(i, j);
if (k == i) {
if (deep[OK[j]] <= deep[i] && up[j] - up[i] == -((s[i] == '('? +1: -1))) {
ans++;
}
continue;
}
if (k == j) {
if (deep[ok[i]] <= deep[j] && up[i] - up[j] == -((s[j] == '('? +1: -1)))
ans++;
continue;
}
if (deep[ok[i]] <= deep[k] && deep[OK[j]] <= deep[k] && up[i] - up[k] + up[j] - up[k] == -((s[k] == '('? +1: -1)))
ans++;
}
cout << ans << "\n";
return 0;
}
for (int T = 0; T < 2; T++) {
for (int i = n - 1; ~i; i--) {
ls[i] = -1;
if (s[i] == ')')
continue;
if (i == n - 1)
continue;
int ind = i + 1;
while (ind < n && s[ind] == '(' && ls[ind] != -1)
ind = ls[ind] + 1;
if (ind == n)
continue;
if (s[ind] == '(')
continue;
ls[i] = ind;
dp[i] = 1 + dp[ind + 1];
}
for (int i = 0; i < n; i++)
ans += dp[i];
reverse(s.begin(), s.end());
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
21504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
33548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
21504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
