#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
const int N=1e2+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
char c[N];
int qan=0;
vector<int> g[N],vc;
int sz[N],ans;
bool col[N];
void dfssz(int v,int par=-1){
sz[v]=1;
qan++;
trav(to,g[v]){
if (col[to] || to==par) continue;
dfssz(to,v);
sz[v]+=sz[to];
}
}
int get(int v,int par=-1){
trav(to,g[v]){
if (col[to] || to==par) continue;
if (sz[to]>qan/2) return get(to,v);
}
return v;
}
set<pir> s;
set<pir>::iterator it;
void dfs1(int v,int pr,int mn,int par=-1){
//if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
if (c[v]=='('){
pr++;
mn++;
mn=min(mn,1);
}
else{
pr--;
mn--;
mn=min(mn,-1);
}
//if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
if (mn>=0){
it=s.lower_bound({pr,INT_MIN});
if (it==s.end() || it->fr!=pr){
s.insert({pr,1});
//cout<<v<<" "<<pr<<endl;
}
else{
pir tv=*it;
tv.sc++;
s.erase(it);
s.insert(tv);
//cout<<pr<<endl;
}
}
trav(to,g[v])if (!col[to] && par!=to)dfs1(to,pr,mn,v);
}
void dfs2(int v,int pr,int mn,int par=-1){
if (c[v]=='('){
pr++;
}
else{
pr--;
}
mn=min(mn,pr);
if (mn==pr){
vc.ad(pr);
//cout<<"hey "<<pr<<endl;
}
trav(to,g[v])if (!col[to] && par!=to)dfs2(to,pr,mn,v);
}
void decomp(int v){
qan=0;
dfssz(v);
int cent=get(v);
//cout<<cent<<endl;
FOR(i,g[cent].size()){
int to=g[cent][i];
if (col[to])continue;
dfs2(to,0,0,cent);
trav(tv,vc){
it=s.lower_bound({-tv,INT_MIN});
if (it->fr==-tv){
ans+=it->sc;
}
}
vc.clear();
if (c[cent]=='(')
dfs1(to,1,1,cent);
else dfs1(to,-1,-1,cent);
}
while(!s.empty())s.erase(s.begin());
if (c[cent]=='(')s.insert({1,1});
FORD(i,g[cent].size()){
int to=g[cent][i];
if (col[to])continue;
dfs2(to,0,0,cent);
trav(tv,vc){
//if (c[cent]=='C' && tv==-1)ans++;
it=s.lower_bound({-tv,INT_MIN});
if (it->fr==-tv){
ans+=it->sc;
}
}
vc.clear();
if (c[cent]=='(')
dfs1(to,1,1,cent);
else dfs1(to,-1,-1,cent);
}
it=s.lower_bound({0,INT_MIN});
//cout<<cent<<" "<<ans<<endl;
if (it->fr==0){
ans+=it->sc;
}
while(!s.empty())s.erase(s.begin());
col[cent]=true;
trav(to,g[cent]){
if (!col[to])decomp(to);
}
}
int main(){
fastio;
srng;
#ifdef ALEXPC
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
FORT(i,1,n){
cin>>c[i];
}
FOR(i,n-1){
int a,b;
cin>>a>>b;
g[a].ad(b);
g[b].ad(a);
}
decomp(1);
cout<<ans<<endl;
return 0;
}
Compilation message
zagrade.cpp: In function 'void decomp(int)':
zagrade.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
zagrade.cpp:107:5: note: in expansion of macro 'FOR'
FOR(i,g[cent].size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
