#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HaBFkZ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
int main(){
_3HaBFkZ;
int n; cin>>n;
string s; cin>>s;
vi a;
for(auto ch : s) a.pb(ch-'0');
vec(vi) adj(n);
rep(i,n-1){
int u,v;
cin>>u>>v;
u--,v--;
adj[u].pb(v);
adj[v].pb(u);
}
vi contains;
auto dfs=[&](auto self,int v,int par)->bool{
bool pokita=!a[v];
for(auto u : adj[v]){
if(u!=par){
bool now=self(self,u,v);
pokita=pokita or now;
}
}
return contains[v]=pokita;
};
vec(vi) fdp;
auto fdfs=[&](auto self,int v,int par)->void{
int chsv=0;
for(auto u : adj[v]){
if(u!=par and contains[u]){
self(self,u,v);
chsv++;
}
}
int state=a[v];
state^=((chsv+1)%2);
int _sum=0;
for(auto u : adj[v]){
if(u!=par and contains[u]){
_sum+=min(fdp[u][0]+4,fdp[u][1]+2);
}
}
fdp[v][state]=_sum;
};
vec(vi) gdp;
auto gdfs=[&](auto self,int v,int par)->void{
int chsv=0;
for(auto u : adj[v]){
if(u!=par and contains[v]){
self(self,u,v);
chsv++;
}
}
gdp[v][0]=fdp[v][1];
gdp[v][1]=fdp[v][1];
vi candies;
for(auto u : adj[v]){
if(u!=par and contains[v]){
candies.pb(u);
}
}
for(auto u : candies){
int _sum=gdp[u][1]+1;
int state=a[v];
for(auto u1 : candies){
if(u==u1) continue;
_sum+=min(fdp[u][0]+3,gdp[u][0]+2);
}
state^=(chsv%2);
// if(v==1) cout<<_sum<<"\n";
if(state==0){
gdp[v][1]=min(gdp[v][1],_sum+3);
}else{
gdp[v][1]=min(gdp[v][1],_sum);
}
}
};
auto solve=[&](int v){
// solve fdp when rooted at v , you walk every subtree twice
contains=vi(n,0);
dfs(dfs,v,-1);
fdp=vec(vi)(n,vi(2,1e9));
fdfs(fdfs,v,-1);
gdp=vec(vi)(n,vi(2,1e9));
gdfs(gdfs,v,-1);
// rep(u,n){
// cout<<gdp[u][1]<<" ";
// }
return gdp[v][1];
// cout<<gdp[v][1]<<"\n";
// cout<<gdp[v][1]<<"\n";
};
int ans=solve(0)+1;
// rep(v,n){
// ans=min(ans,solve(v)+1);
// cout<<solve(v)<<" ";
// // solve(v);
// }
cout<<ans<<"\n";
//
return 0;
}
Compilation message
svjetlo.cpp: In instantiation of 'main()::<lambda(auto:23, int, int)> [with auto:23 = main()::<lambda(auto:23, int, int)>]':
svjetlo.cpp:98:16: required from here
svjetlo.cpp:41:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
41 | return contains[v]=pokita;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
442 ms |
97540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
506 ms |
72332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
