#include <bits/stdc++.h>
// author: aykhn
using namespace std;
#define int long long
#define inf 0x3F3F3F3F
const int MXN = 1e5 + 5;
int n;
vector<int> adj[MXN];
int val[MXN], dp[MXN][2][2];
// dp[i][j][k] = j by doing k ops and ok subtree
void dfs(int a, int p)
{
vector<int> v1;
int f = 0;
for (int v : adj[a])
{
if (v == p) continue;
f = 1;
dfs(v, a);
v1.push_back(v);
}
if (!f)
{
if (!val[a]) dp[a][0][0] = 0, dp[a][0][1] = inf, dp[a][1][0] = inf, dp[a][1][1] = 1;
else dp[a][0][0] = inf, dp[a][0][1] = 1, dp[a][1][0] = 0, dp[a][1][1] = inf;
return;
}
if (!val[a])
{
dp[a][0][0] = 0;
vector<int> nw;
for (int v : v1)
{
dp[a][0][0] += dp[v][0][0];
nw.push_back(dp[v][0][1] - dp[v][0][0]);
}
sort(nw.begin(), nw.end());
int s = 0, mn = 0;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 1) mn = min(mn, s);
}
dp[a][0][0] += mn;
//---
dp[a][0][1] = 1;
nw.clear();
for (int v : v1)
{
dp[a][0][1] += dp[v][1][0];
nw.push_back(dp[v][1][1] - dp[v][1][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = inf;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 0) mn = min(mn, s);
}
dp[a][0][1] += mn;
//---
dp[a][1][0] = 0;
nw.clear();
for (int v : v1)
{
dp[a][1][0] += dp[v][0][0];
nw.push_back(dp[v][0][1] - dp[v][0][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = inf;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 0) mn = min(mn, s);
}
dp[a][1][0] += mn;
//---
dp[a][1][1] = 1;
nw.clear();
for (int v : v1)
{
dp[a][1][1] += dp[v][1][0];
nw.push_back(dp[v][1][1] - dp[v][1][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = 0;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 1) mn = min(mn, s);
}
dp[a][1][1] += mn;
}
else
{
dp[a][0][0] = 0;
vector<int> nw;
for (int v : v1)
{
dp[a][0][0] += dp[v][0][0];
nw.push_back(dp[v][0][1] - dp[v][0][0]);
}
sort(nw.begin(), nw.end());
int s = 0, mn = inf;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 0) mn = min(mn, s);
}
dp[a][0][0] += mn;
//---
dp[a][0][1] = 1;
nw.clear();
for (int v : v1)
{
dp[a][0][1] += dp[v][1][0];
nw.push_back(dp[v][1][1] - dp[v][1][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = 0;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 1) mn = min(mn, s);
}
dp[a][0][1] += mn;
//---
dp[a][1][0] = 0;
nw.clear();
for (int v : v1)
{
dp[a][1][0] += dp[v][0][0];
nw.push_back(dp[v][0][1] - dp[v][0][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = 0;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 1) mn = min(mn, s);
}
dp[a][1][0] += mn;
//---
dp[a][1][1] = 1;
nw.clear();
for (int v : v1)
{
dp[a][1][1] += dp[v][1][0];
nw.push_back(dp[v][1][1] - dp[v][1][0]);
}
sort(nw.begin(), nw.end());
s = 0, mn = inf;
for (int i = 0; i < nw.size(); i++)
{
s += nw[i];
if (i % 2 == 0) mn = min(mn, s);
}
dp[a][1][1] += mn;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) cin >> val[i];
dfs(1, 1);
if (dp[1][0][1] >= inf && dp[1][0][0] >= inf)
{
cout << "impossible\n";
return 0;
}
cout << min(dp[1][0][1], dp[1][0][0]) << '\n';
}
//
Compilation message
xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:43:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:59:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:75:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:91:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:109:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:125:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:141:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
xanadu.cpp:157:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (int i = 0; i < nw.size(); i++)
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
2 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
2 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4440 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4292 KB |
Output is correct |
11 |
Correct |
2 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4456 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
25264 KB |
Output is correct |
2 |
Correct |
45 ms |
25180 KB |
Output is correct |
3 |
Correct |
49 ms |
25276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
25232 KB |
Output is correct |
2 |
Correct |
50 ms |
24912 KB |
Output is correct |
3 |
Correct |
47 ms |
25428 KB |
Output is correct |
4 |
Correct |
49 ms |
10204 KB |
Output is correct |
5 |
Correct |
46 ms |
10580 KB |
Output is correct |
6 |
Correct |
41 ms |
10576 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
14 ms |
8028 KB |
Output is correct |
9 |
Correct |
47 ms |
10636 KB |
Output is correct |
10 |
Correct |
63 ms |
10652 KB |
Output is correct |
11 |
Correct |
43 ms |
11544 KB |
Output is correct |
12 |
Correct |
52 ms |
11612 KB |
Output is correct |
13 |
Correct |
40 ms |
10736 KB |
Output is correct |
14 |
Correct |
46 ms |
10840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
2 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4440 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4292 KB |
Output is correct |
11 |
Correct |
2 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4456 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
46 ms |
25264 KB |
Output is correct |
18 |
Correct |
45 ms |
25180 KB |
Output is correct |
19 |
Correct |
49 ms |
25276 KB |
Output is correct |
20 |
Correct |
50 ms |
25232 KB |
Output is correct |
21 |
Correct |
50 ms |
24912 KB |
Output is correct |
22 |
Correct |
47 ms |
25428 KB |
Output is correct |
23 |
Correct |
49 ms |
10204 KB |
Output is correct |
24 |
Correct |
46 ms |
10580 KB |
Output is correct |
25 |
Correct |
41 ms |
10576 KB |
Output is correct |
26 |
Correct |
1 ms |
4440 KB |
Output is correct |
27 |
Correct |
14 ms |
8028 KB |
Output is correct |
28 |
Correct |
47 ms |
10636 KB |
Output is correct |
29 |
Correct |
63 ms |
10652 KB |
Output is correct |
30 |
Correct |
43 ms |
11544 KB |
Output is correct |
31 |
Correct |
52 ms |
11612 KB |
Output is correct |
32 |
Correct |
40 ms |
10736 KB |
Output is correct |
33 |
Correct |
46 ms |
10840 KB |
Output is correct |
34 |
Correct |
2 ms |
4444 KB |
Output is correct |
35 |
Correct |
1 ms |
4444 KB |
Output is correct |
36 |
Correct |
2 ms |
4444 KB |
Output is correct |
37 |
Correct |
1 ms |
4444 KB |
Output is correct |
38 |
Correct |
1 ms |
4444 KB |
Output is correct |
39 |
Correct |
2 ms |
4440 KB |
Output is correct |
40 |
Correct |
2 ms |
4696 KB |
Output is correct |
41 |
Correct |
1 ms |
4444 KB |
Output is correct |
42 |
Correct |
1 ms |
4444 KB |
Output is correct |
43 |
Correct |
3 ms |
4444 KB |
Output is correct |
44 |
Correct |
2 ms |
4444 KB |
Output is correct |
45 |
Correct |
49 ms |
25180 KB |
Output is correct |
46 |
Correct |
47 ms |
25000 KB |
Output is correct |
47 |
Correct |
50 ms |
25428 KB |
Output is correct |
48 |
Correct |
37 ms |
10072 KB |
Output is correct |
49 |
Correct |
41 ms |
10588 KB |
Output is correct |
50 |
Correct |
52 ms |
10716 KB |
Output is correct |
51 |
Correct |
2 ms |
4440 KB |
Output is correct |
52 |
Correct |
15 ms |
8028 KB |
Output is correct |
53 |
Correct |
42 ms |
10452 KB |
Output is correct |
54 |
Correct |
41 ms |
10328 KB |
Output is correct |
55 |
Correct |
61 ms |
11552 KB |
Output is correct |
56 |
Correct |
43 ms |
11612 KB |
Output is correct |
57 |
Correct |
40 ms |
10572 KB |
Output is correct |
58 |
Correct |
41 ms |
10836 KB |
Output is correct |
59 |
Correct |
17 ms |
7768 KB |
Output is correct |
60 |
Correct |
36 ms |
10080 KB |
Output is correct |
61 |
Correct |
51 ms |
10312 KB |
Output is correct |
62 |
Correct |
45 ms |
10324 KB |
Output is correct |
63 |
Correct |
43 ms |
10320 KB |
Output is correct |
64 |
Correct |
42 ms |
10364 KB |
Output is correct |
65 |
Correct |
40 ms |
10832 KB |
Output is correct |
66 |
Correct |
39 ms |
10708 KB |
Output is correct |
67 |
Correct |
35 ms |
12916 KB |
Output is correct |
68 |
Correct |
33 ms |
12884 KB |
Output is correct |
69 |
Correct |
34 ms |
12884 KB |
Output is correct |
70 |
Correct |
33 ms |
12884 KB |
Output is correct |