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 <iostream>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, val[300005], ss[300005], br;
ll dp[300005], sol;
char s[300005];
vector <int> ms[300005];
bool bio[300005];
inline void dfs1(int x, int p){
br++;
ss[x] = 1;
for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = *i;
if(o == p || bio[o])
continue;
dfs1(o, x);
ss[x] += ss[o];
}
}
inline int dfs2(int x, int p){
for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = *i;
if(o == p || bio[o])
continue;
if(ss[o] > br / 2)
return dfs2(o, x);
}
return x;
}
inline void processdp(int x, int p, int sad, int sve, int add){
sad = (val[x] == 1 ? max(1, sad + 1) : sad - 1);
sve -= (sad < 0);
if(sad <= 0){
dp[-sve] += add;
}
for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = *i;
if(o == p || bio[o])
continue;
processdp(o, x, sad, sve, add);
}
}
inline void dfs3(int x, int p, int sad, int sve){
sad = (val[x] == -1 ? min(-1, sad - 1) : sad + 1);
sve += (sad > 0);
if(sad >= 0){
sol += dp[sve];
}
for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = *i;
if(o == p || bio[o])
continue;
dfs3(o, x, sad, sve);
}
}
inline void decompose(int root){
dfs1(root, -1);
int centroid = dfs2(root, -1);
bio[centroid] = 1;
processdp(centroid, -1, 0, 0, 1);
sol += dp[0];
for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
int o = *i;
if(bio[o])
continue;
processdp(o, centroid, val[centroid], min(0, val[centroid]), -1);
dfs3(o, centroid, 0, 0);
processdp(o, centroid, val[centroid], min(0, val[centroid]), 1);
}
//cout << centroid << ' ' << sol << endl;
processdp(centroid, -1, 0, 0, -1);
for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
int o = *i;
if(bio[o])
continue;
decompose(o);
}
}
int main(){
scanf("%d", &n);
scanf("%s", &s);
for(int i = 0 ; i < n ; ++i){
if(s[i] == '('){
val[i + 1] = 1;
}
else{
val[i + 1] = -1;
}
}
for(int i = 0 ; i < n - 1 ; ++i){
int x, y;
scanf("%d %d", &x, &y);
ms[x].push_back(y);
ms[y].push_back(x);
}
decompose(1);
printf("%lld\n", sol);
return 0;
}
Compilation message (stderr)
zagrade.cpp: In function 'int main()':
zagrade.cpp:92:15: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
scanf("%s", &s);
~~^
zagrade.cpp:91:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
zagrade.cpp:92:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &s);
~~~~~^~~~~~~~~~
zagrade.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |