#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;
map <int,int> cnt[2];
vector <int> adj[M], v[M];
int n, c[M], pref[M], sz[M], ans, dep[M], mn[M][20], anc[M][0];
void calc(int node, int p){
sz[node] = 1;
for(auto i : adj[node]) if(i != p){
pref[i] = pref[node] + c[i];
dep[i] = dep[node] + 1;
mn[i][0] = pref[node];
anc[i][0] = node;
calc(i, node);
sz[node] += sz[i];
}
return;
}
int get(int a, int b){
int ret = pref[a];
for(int i = 17; i >= 0; --i) if(dep[anc[a][i]] >= dep[b]){
ret = min(ret, mn[a][i]);
a = anc[a][i];
}
return ret;
}
void dfs(int node, int p, bool keep){
int big = 0;
for(auto i : adj[node]) if(i != p && sz[i] > sz[big]) big = i;
for(auto i : adj[node]) if(i != p && i != big) dfs(i, node, 0);
if(big){
dfs(big, node, 1);
swap(v[node], v[big]);
}
v[node].pb(node);
for(auto i : adj[node]) if(i != p && i != big){
for(auto j : v[i]){
int mn = get(j, node);
if(mn - pref[node] + c[node] >= 0) ans += cnt[1][-(pref[j] - pref[node] + c[node])];
if(pref[j] - pref[node] <= 0) ans += cnt[0][-(pref[j] - pref[node])];
}
for(auto j : v[i]){
int mn = get(j, node);
if(mn - pref[node] + c[node] >= 0) ++cnt[0][pref[j] - pref[node] + c[node]];
if(pref[j] - pref[node] <= 0) ++cnt[1][pref[j] - pref[node]];
}
for(auto j : v[i]) v[node].pb(j);
}
if(!keep){
for(auto i : v[node]){
cnt[0][pref[i] - pref[node] + c[node]] = 0;
cnt[1][pref[i] - pref[node]] = 0;
}
}
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
char x; cin >> x;
c[i] = (x == '(' ? 1 : -1);
}
for(int i = 1; i < n; ++i){
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dep[1] = 1;
calc(1, 0);
for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
dfs(1, 0, 1);
cout << ans << endl;
return 0;
}
Compilation message
zagrade.cpp: In function 'void calc(int, int)':
zagrade.cpp:29:17: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds]
29 | anc[i][0] = node;
| ~~~~~~~~^
zagrade.cpp: In function 'int get(int, int)':
zagrade.cpp:40:49: warning: array subscript i is outside array bounds of 'int [0]' [-Warray-bounds]
40 | for(int i = 17; i >= 0; --i) if(dep[anc[a][i]] >= dep[b]){
| ~~~~~~~~^
zagrade.cpp: In function 'int main()':
zagrade.cpp:101:89: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
101 | for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
| ~~~~~~~~~~~~^
zagrade.cpp:101:97: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
101 | for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
| ~~~~~~~~~~~~~~~~~~~~~~~~^
zagrade.cpp:101:69: warning: array subscript j is outside array bounds of 'int [0]' [-Warray-bounds]
101 | for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
| ~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
