#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll tin[N],tout[N],h[N],timer,a[N],ans,dp[N],pr[20][N];
string s;
vector<ll>g[N];
void dfs(ll v){
tin[v]=++timer;
for(ll i=1;i<=19;i++)pr[i][v]=pr[i-1][pr[i-1][v]];
for(ll to:g[v]){
if(to==pr[0][v])continue;
pr[0][to]=v;
dfs(to);
}
tout[v]=timer;
}
bool is_parent(ll x,ll y){
return (tin[x]<=tin[y]&&tout[y]<=tout[x]);
}
ll get(ll x,ll y){
for(ll i=19;i>=0;i--){
if(!is_parent(pr[i][x],y))x=pr[i][x];
}if(!is_parent(x,y))return pr[0][x];
return x;
}
ll cnt=0,sub=0;
void calc(ll v,ll pr=0){
if(sub){
cout<<v<<' '<<dp[v]<<'\n';
}
for(ll to:g[v]){
if(to==pr)continue;
calc(to,v);
dp[v]+=dp[to];
}
if(s[v]=='1'&&dp[v]){
cnt++;
if(a[v])cnt++;
if(sub)cout<<v<<'\n';
}
}
//}ll cnt(ll v,ll u){
// ll lca=get(v,u);
// return h[u]+h[v]-2*h[lca]+(s[lca]-'0');
//}
ll n;
void f(ll x,ll sum){
if(x==n){
// sub=(sum==4&&a[1]&&a[8]&&a[5]&&a[7]);
for(ll i=1;i<=n;i++)dp[i]=0;
for(ll i=1;i<=n;i++){
if(!a[i])continue;
for(ll j=i+1;j<=n;j++){
if(!a[j])continue;
// if(sub)cout<<j<<' '<<pr[i]<<'\n';
// if(is_parent(j,i)){
// swp=1;
// swap(i,j);
// }
ll x=get(i,j);
// if(sum==4){
// cout<<x<<' '<<i<<' '<<j<<'\n';
// }
if(x==i){
dp[pr[0][j]]++;
dp[x]--;
continue;
}if(x==j){
dp[pr[0][i]]++;
dp[x]--;
continue;
}
dp[pr[0][i]]++;
if(x!=1)dp[pr[0][x]]--;
// if(sub)cout<<i<<' '<<pr[0][x]<<'\n';
dp[pr[0][j]]++;
dp[x]--;
// if(sub)cout<<j<<' '<<pr[0][x]<<'\n';
// if(swp)swap(i,j);
}
}
cnt=0;
calc(1);
// if(sum-cnt==4){
// for(ll i=1;i<=n;i++)cout<<a[i]<<' ';
// cout<<'\n';
// }
ans=max(ans,sum-cnt);
return;
}
x++;
a[x]=0;
f(x,sum);
if(s[x]=='1'){
a[x]=1;
f(x,sum+1);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(ll i=1;i<n;i++){
ll v,u;
cin>>v>>u;
g[v].push_back(u);
g[u].push_back(v);
}
cin>>s;
pr[0][1]=1;
s=' '+s;
dfs(1);
// a[1]=1;
// a[2]=1;
// a[5]=1;
f(0,0);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |