Submission #783987

#TimeUsernameProblemLanguageResultExecution timeMemory
783987kebineThe Xana coup (BOI21_xanadu)C++17
100 / 100
99 ms18036 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cur[100005];
vector <ll> al[100005];
ll vis[100005];
ll dp[100005][2][2];
void dfs(ll node){
    vis[node]=1;
    if (cur[node]==1){
        dp[node][1][0]+=1;
        dp[node][0][1]+=0;
        dp[node][0][0]+=1e9;
        dp[node][1][1]+=1e9;
    }
    else{
        dp[node][1][0]+=1e9;
        dp[node][0][1]+=1e9;
        dp[node][0][0]+=0;
        dp[node][1][1]+=1;
    }
    for (auto u:al[node]){
        if (vis[u]!=1){
            vis[u]=1;
            dfs(u);
            ll x=dp[node][0][0], y=dp[node][0][1];
            dp[node][0][0]=min(x+dp[u][0][0],y+dp[u][1][0]);
            dp[node][0][1]=min(y+dp[u][0][0],x+dp[u][1][0]);
            ll a=dp[node][1][0],b=dp[node][1][1];
            dp[node][1][0]=min(a+dp[u][0][1],b+dp[u][1][1]);
            dp[node][1][1]=min(b+dp[u][0][1],a+dp[u][1][1]);
        }
    }
}
int main(){
    cin>>n;
    for (int i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        al[a].push_back(b);
        al[b].push_back(a);
    }
    for (int i=1;i<=n;i++){
        cin>>cur[i];
    }
    dfs(1);
    ll ans=min(dp[1][0][0],dp[1][1][0]);
    if (ans>n) cout<<"impossible";
    else cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...