| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1106183 | alexdd | The Xana coup (BOI21_xanadu) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}