#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define arr array<int, 2>
int inf = 1e9;
vector<vector<int>> graph;
vector<int> state;
vector<array<arr, 2>> opt;
void dfs(int i, int p)
{
opt[i][0][0] = inf;
opt[i][0][1] = inf;
opt[i][1][0] = inf;
opt[i][1][1] = inf;
if (graph[i].size() == 1 && i != 0)
{
int s = state[i];
opt[i][s][0] = 0;
opt[i][s][1] = inf;
if (s == 1) s = 0;
else s = 1;
opt[i][s][0] = inf;
opt[i][s][1] = 1;
return;
}
vector<int> on;
vector<int> off;
int sumon = 0;
int sumoff = 0;
for (int ele:graph[i])
{
if (ele == p) continue;
dfs(ele, i);
sumon += opt[ele][1][0];
on.push_back(opt[ele][1][1]-opt[ele][1][0]);
sumoff += opt[ele][0][0];
off.push_back(opt[ele][0][1]-opt[ele][0][0]);
}
sort(on.begin(), on.end(), less<int>());
sort(off.begin(), off.end(), less<int>());
int s = state[i];
int ns;
if (s == 0) ns = 1;
else ns = 0;
for (int j = 0; j <= on.size(); j++)
{
if (j%2) opt[i][s][1] = min(opt[i][s][1], sumon+1);
else opt[i][ns][1] = min(opt[i][ns][1], sumon+1);
if (j < on.size()) sumon+=on[j];
}
for (int j = 0; j <= off.size(); j++)
{
if (j%2) opt[i][ns][0] = min(opt[i][ns][0], sumoff);
else opt[i][s][0] = min(opt[i][s][0], sumoff);
if (j < off.size()) sumoff+=off[j];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n;
cin >> n;
graph.assign(n, vector<int>());
state.assign(n, 0);
opt.assign(n, array<arr, 2>());
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 0; i < n; i++) cin >> state[i];
dfs(0, -1);
/*
for (int i = 0; i < n; i++)
{
cout << opt[i][0][0] << " " << opt[i][0][1] << endl;
cout << opt[i][1][0] << " " << opt[i][1][1] << endl;
}
*/
int mn = min(opt[0][0][0], opt[0][0][1]);
if (mn > n) cout << "impossible\n";
else cout << mn << "\n";
return 0;
}
Compilation message
xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int j = 0; j <= on.size(); j++)
| ~~^~~~~~~~~~~~
xanadu.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (j < on.size()) sumon+=on[j];
| ~~^~~~~~~~~~~
xanadu.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j = 0; j <= off.size(); j++)
| ~~^~~~~~~~~~~~~
xanadu.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if (j < off.size()) sumoff+=off[j];
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
26448 KB |
Output is correct |
| 2 |
Correct |
45 ms |
26192 KB |
Output is correct |
| 3 |
Correct |
46 ms |
26508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
26452 KB |
Output is correct |
| 2 |
Correct |
47 ms |
26196 KB |
Output is correct |
| 3 |
Correct |
53 ms |
26452 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
7000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
