| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 894974 | vjudge1 | Zagrade (COI17_zagrade) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
const ld PI = 3.1415926535;
const int N = 3e5 + 2;
const int M = 7e6 + 1;
int mod0 = 1e9+7, mod1 = 1e9+9;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;
int mult(int a, int b, int mod) {
return a * 1LL * b % mod;
}
int sum(int a, int b, int mod) {
a %= mod;
if (a + b < 0)
return a + b + mod;
if (a + b >= mod)
return a + b - mod;
return a + b;
}
ll binpow(ll a, ll n, int mod) {
if (n == 0)
return 1;
if (n % 2 == 1) {
return binpow(a, n - 1, mod) * a % mod;
} else {
ll b = binpow(a, n / 2, mod);
return b * b % mod;
}
}
vector<int> g[N], ng[N];
int pc[N], used[N], sz[N], d[N];
void recalcsz(int v, int p){
sz[v] = 1;
for(auto u : g[v]){
if(u != p && !used[u]){
recalcsz(u, v);
sz[v] += sz[u];
}
}
}
int getcentroid(int v, int p, int wh){
for(auto u : g[v]){
if(u != p && !used[u] && sz[u] > (wh / 2))
return getcentroid(u, v, wh);
}
return v;
}
void decompose(int v, int p, int dp = 1){
pc[v] = p;
used[v] = 1;
d[v] = dp;
for(auto u : g[v]){
if(!used[u]){
recalcsz(u, -1);
int c = getcentroid(u, -1, sz[u]);
decompose(c, v, dp + 1);
}
}
}
unordered_map<int, pii> mp[N], mp1[N];
string s = "";
int ans;
vector<int> dfs1(int v){
vector<int> vs[sz(ng[v])];
unordered_map<int, int> mpp;
vector<int> ret = {v};
for(int i = 0; i < sz(ng[v]); i++){
vs[i] = dfs1(ng[v][i]);
for(auto u : vs[i]){
ret.pb(u);
if(mp[u][v].S >= 0){
if(s[v] == ')' && mp[u][v].F == 1)
ans++;
ans += mpp[-mp[u][v].F];
}
}
for(auto u : vs[i]){
if(mp1[v][u].S >= mp1[v][u].F){
mpp[mp1[v][u].F]++;
if(mp1[v][u].F == 0)
ans++;
}
}
}
mpp.clear();
for(int i = sz(ng[v]) - 1; i >= 0; i--){
for(auto u : vs[i]){
if(mp[u][v].S >= 0){
ans += mpp[-mp[u][v].F];
}
}
for(auto u : vs[i]){
if(mp1[v][u].S >= mp1[v][u].F)
mpp[mp1[v][u].F]++;
}
}
return ret;
}
void nudela(int v, int p, int r, int c, int mn){
if(s[v] == '(')
c++;
else
c--;
mn = min(mn, c);
mp1[r][v] = {c, mn};
for(auto u : g[v]){
if(u != p && d[u] > d[r])
nudela(u, v, r, c, mn);
}
}
void neveroyatno(int v, int p, int r, int ver, int mn){
if(v != r){
if(s[v] == '(')
mn = min(mn + 1, 0), ver++;
else
mn = min(mn - 1, -1), ver--;
mp[v][r] = {ver, mn};
}
for(auto u : g[v]){
if(d[u] > d[r] && u != p)
neveroyatno(u, v, r, ver, mn);
}
}
void solve(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
int c = rand() % 2;
if(c)
s += "(";
else
s += ")";
}
cin >> s;
s = "@" + s;
for(int i = 1; i < n; i++){
int u = i, v = i + 1;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
recalcsz(1, -1);
int c = getcentroid(1, -1, sz[1]);
decompose(c, -1);
for(int i = 1; i <= n; i++)
ng[pc[i]].pb(i);
for(int i = 1; i <= n; i++)
nudela(i, -1, i, 0, 0);
for(int i = 1; i <= n; i++)
neveroyatno(i, -1, i, 0, 0);
/*for(int i = 1; i <= n; i++)
cout << d[i] << ' ';
//cout << '\n';
for(auto e : mp){
//cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
}
//cout << '\n';
for(auto e : mp1){
//cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
}*/
dfs1(c);
cout << ans << '\n';
}
signed main() {
mispertion;
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}