#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define int long long
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,t,vis[li],sub[li];
int cev;
char s[li];
map<int,int> mpp,mpp1;
vector<int> v[li];
inline void dfs(int node,int ata){
sub[node]=1;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go])continue;
dfs(go,node);
sub[node]+=sub[go];
}
}
inline int find_centroid(int node,int ata,int sz){
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go]==1)continue;
if(sub[go]>sz/2)return find_centroid(go,node,sz);
dfs(go,node);
}
return node;
}
inline void upd1(int node,int ata,int der,int mx){
if(der>=0 && der>=mx)mpp[der]++;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go])continue;
int at=der+(s[go]==')'?1:-1);
if(at<0)continue;
upd1(go,node,at,max(at,mx));
}
}
inline void upd2(int node,int ata,int der,int kts,int mx){
//~ cout<<der<<"whyy"<<endl;
if(kts==0 && der>=0 && der>=mx)mpp[der]--;
if(kts==1 && der>=0 && der>=mx)mpp[der]++;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go])continue;
int at=der+(s[go]==')'?1:-1);
if(at<0)continue;
upd2(go,node,at,kts,max(mx,at));
}
}
inline void query(int node,int ata,int der){
//~ cout<<"()"<<der<<"()"<<node<<"()"<<mpp[0]<<"()"<<endl;
if(der>=0)cev+=mpp[der];
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go])continue;
//~ if(go==4){cout<<"mpp"<<mpp[0]<<"mpp"<<endl;}
int at=der+(s[go]==')'?-1:1);
query(go,node,at);
}
}
inline void dfs2(int node,int ata,int der,int der1,int flag){
if(der==0 && flag==1)cev++;
if(der1==0 && flag==0)cev++;
//~ cout<<der1<<"&&"<<endl;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
if(vis[go])continue;
if(flag==1 && der+(s[go]==')'?-1:1)<0){continue;}
if(flag==0 && der1+(s[go]==')'?1:-1)<0){continue;}
dfs2(go,node,der+(s[go]==')'?-1:1),der1+(s[go]==')'?1:-1),flag);
}
}
inline void solve(int node){
dfs(node,0);
//~ cout<<node<<endl;
int c=find_centroid(node,0,sub[node]);
mpp.clear();
mpp1.clear();
//~ mpp[0]++;
//~ cout<<c<<" : ; "<<s[c]<<endl;
//~ int at=(s[c]==')'?-1:1);
//~ int at1=(s[c]==')'?1:-1);
//~ cout<<at1<<"()()"<<endl;
upd1(c,0,0,0);
//~ cout<<mpp[0]<<"why\n";
//~ dfs2(c,0,at,at1,(at>at1?1:0));
//~ cout<<cev<<"**\n";
//~ cout<<c<<"()\n";
for(int i=0;i<(int)v[c].size();i++){
int go=v[c][i];
if(vis[v[c][i]])continue;
//~ int okk=0,okk1=0;
//~ cout<<"OO"<<c<<"OO"<<go<<"OO\n";
if(s[go]==')'){
//~ cout<<"**\n";
upd2(go,c,1,0,0);
//~ cout<<"II"<<mpp[0]<<"II"<<endl;
query(go,c,-1+(s[c]=='('?1:-1));
}
else{
//~ upd2(go,c,-1,0);
query(go,c,1+(s[c]=='('?1:-1));
}
if(s[go]==')'){
upd2(go,c,1,1,0);
}
else{
//~ upd2(go,c,-1,1);
}
//~ cout<<cev<<"**"<<endl;
}
//~ printf("\n");
vis[c]=1;
for(int i=0;i<(int)v[c].size();i++){
if(vis[v[c][i]])continue;
solve(v[c][i]);
}
}
main(void){
fio();
cin>>n>>(s+1);
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
solve(1);
//~ mpp[0]++;
cout<<cev<<endl;
return 0;
}
Compilation message
zagrade.cpp:160:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(void){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
36216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
