#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll 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<ll,ll>;
using vi=vector<ll>;
int main(){
_3HaBFkZ;
ll 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){
ll u,v;
cin>>u>>v;
u--,v--;
adj[u].pb(v);
adj[v].pb(u);
}
vi contains;
auto dfs=[&](auto self,ll v,ll 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,ll v,ll par)->void{
ll state=a[v];
fdp[v][state^1]=0;
for(auto u : adj[v]){
if(u!=par and contains[u]){
self(self,u,v);
vi nedp(2,1e9);
rep(t,2){
nedp[t]=min(nedp[t],fdp[v][t]+fdp[u][0]+4);
nedp[t^1]=min(nedp[t^1],fdp[v][t]+fdp[u][1]+2);
}
fdp[v]=nedp;
}
}
};
vec(vec(vi)) gdp(n,vec(vi)(2,vi(2,1e9)));
// vertex,color,primary_way
auto gdfs=[&](auto self,ll v,ll par)->void{
ll chsv=0;
for(auto u : adj[v]){
if(u!=par and contains[v]){
self(self,u,v);
chsv++;
}
}
rep(t,2){
gdp[v][t][0]=fdp[v][t];
}
gdp[v][1][1]=fdp[v][1];
for(auto u : adj[v]){
vi now(2,1e9);
now[a[v]^1]=0;
for(auto u1 : adj[v]){
if(u==u1 or u1==par or !contains[u1]) continue;
vi nedp(2,1e9);
rep(t,2){
nedp[t]=min(nedp[t],now[t]+gdp[u1][0][0]+4);
nedp[t^1]=min(nedp[t^1],now[t]+gdp[u1][1][0]+2);
}
now=nedp;
}
// if(v==2) cout<<a[v]<<" ";
now[1]+=gdp[u][1][1]+1;
now[1]=min(now[1],now[0]+gdp[u][1][1]+3);
gdp[v][1][1]=min(gdp[v][1][1],now[1]);
}
// if(v==2){
// cout<<gdp[v][1][1]<<"\n";
// }
};
auto solve=[&](ll v){
contains=vi(n,0);
dfs(dfs,v,-1);
fdp=vec(vi)(n,vi(2,1e9));
fdfs(fdfs,v,-1);
gdp=vec(vec(vi))(n,vec(vi)(2,vi(2,1e9)));
gdfs(gdfs,v,-1);
// cout<<gdp[v][1][1]<<"\n";
return gdp[v][1][1];
};
ll now,ans=1e9;
rep(v,n){
now=solve(v);
ans=min(ans,now+1);
// cout<<now<<" ";
}
cout<<ans<<"\n";
// solve(1);
// now=solve(1);
//
return 0;
}
Compilation message
svjetlo.cpp: In instantiation of 'main()::<lambda(auto:23, ll, ll)> [with auto:23 = main()::<lambda(auto:23, ll, ll)>; ll = long long int]':
svjetlo.cpp:96: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 |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2097 ms |
194424 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
165168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
