| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1106183 | alexdd | The Xana coup (BOI21_xanadu) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
int n;
vector<int> con[100005];
int dp[100005][2][2];//dp[nod][stare_nod][insus]
int a[100005];
void dfs(int nod, int par)
{
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
dp[nod][i][j]=INF;
dp[nod][a[nod]][0]=0;
dp[nod][1-a[nod]][1]=1;
for(int adj:con[nod])
{
if(adj==par)
continue;
dfs(adj,nod);
int old[2][2];
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
old[i][j]=dp[nod][i][j];
for(int v=0;v<2;v++)
{
dp[nod][v][0] = min({INF, old[v][0]+dp[adj][0][0], old[1-v][0]+dp[adj][0][1]});
dp[nod][v][1] = min({INF, old[v][1]+dp[adj][1][0], old[1-v][1]+dp[adj][1][1]});
}
}
}
int main()
{
cin>>n;
int u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
con[u].push_back(v);
con[v].push_back(u);
}
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,0);
int rez = min(dp[1][0][0], dp[1][0][1]);
if(rez>=INF)
cout<<"impossible";
else
cout<<rez;
return 0;
}