Submission #370138

#	Time	Username	Problem	Language	Result	Execution time	Memory
370138		Nima_Naderi	Zagrade (COI17_zagrade)	C++14	100 / 100	1504 ms	49240 KiB

zagrade

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

//typedef long long ll;
typedef int ll;
const ll MXN = 3e5 + 10;
ll n, globc;
long long ans;
ll sub[MXN], bal[MXN], minb[MXN], ted[MXN];
vector<ll> adj[MXN];
bool hide[MXN];
string s;
void plant(ll u, ll par){
    sub[u] = 1;
    for(auto v : adj[u]){
        if(v != par && !hide[v]){
            plant(v, u), sub[u] += sub[v];
        }
    }
}
ll CRD(ll u, ll par, ll val){
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        if(sub[v] >= val) return CRD(v, u, val);
    }
    return u;
}
void Upd(ll u, ll par, ll dt){
    if(par == globc) bal[u] = minb[u] = 0;
    else             bal[u] = bal[par], minb[u] = minb[par];
    bal[u] += (s[u] == '(' ? +1 : -1);
    minb[u] = min(minb[u], bal[u]);
    if(bal[u] <= 0 && minb[u] - bal[u] >= 0){
        ted[-bal[u]] += dt;
    }
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        Upd(v, u, dt);
    }
}
void Calc(ll u, ll par, ll b, ll mb){
    b = (s[u] == '(' ? +1 : -1) + b;
    mb = min(0, (s[u] == '(' ? +1 : -1) + mb);
    if(mb >= 0){
        ans += ted[b];
        if(b == 0) ans ++;
    }
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        Calc(v, u, b, mb);
    }
}
void DMS(ll u, ll h){
    plant(u, -1);
    ll cent = CRD(u, -1, (sub[u] + 1) / 2);
    globc = cent;
    for(auto v : adj[cent]){
        if(!hide[v]) Upd(v, cent, +1);
    }
    for(auto v : adj[cent]){
        if(hide[v]) continue;
        ll x = (s[cent] == '(' ? +1 : -1);
        Upd(v, cent, -1);
        Calc(v, cent, x, min(0, x));
        Upd(v, cent, +1);
    }
    if(s[cent] == '(') ans += ted[1];
    for(auto v : adj[cent]){
        if(!hide[v]) Upd(v, cent, -1);
    }
    hide[cent] = 1;
    for(auto v : adj[cent]){
        if(!hide[v]) DMS(v, h + 1);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = "$" + s;
    for(int i = 1; i < n; i ++){
        ll u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    DMS(1, 0);
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60