#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+7;
const ll P = 31;
const ll LOGN = 20;
const ll MAXN = 1e5 + 100;
#define int long long
vector<vector<int>> graph;
int active[MAXN], dp[MAXN][2][2], temp_dp[2];
void act(int node, int parent) {
temp_dp[0] = 0;
temp_dp[1] = 1e8;
for (auto u : graph[node]) {
if (u == parent)
continue;
int td0 = temp_dp[0], td1 = temp_dp[1];
temp_dp[0] = min(td1 + dp[u][1][1], td0 + dp[u][0][1]);
temp_dp[1] = min(td1 + dp[u][0][1], td0 + dp[u][1][1]);
}
dp[node][1][0] = temp_dp[0] + 1;
dp[node][1][1] = temp_dp[1] + 1;
temp_dp[0] = 0;
temp_dp[1] = 1e8;
for (auto u : graph[node]) {
if (u == parent)
continue;
int td0 = temp_dp[0], td1 = temp_dp[1];
temp_dp[0] = min(td1 + dp[u][1][0], td0 + dp[u][0][0]);
temp_dp[1] = min(td1 + dp[u][0][0], td0 + dp[u][1][0]);
}
dp[node][0][1] = temp_dp[0];
dp[node][0][0] = temp_dp[1];
}
void deact(int node, int parent) {
temp_dp[0] = 0;
temp_dp[1] = 1e8;
for (auto u : graph[node]) {
if (u == parent)
continue;
int td0 = temp_dp[0], td1 = temp_dp[1];
temp_dp[0] = min(td1 + dp[u][1][1], td0 + dp[u][0][1]);
temp_dp[1] = min(td1 + dp[u][0][1], td0 + dp[u][1][1]);
}
dp[node][1][1] = temp_dp[0] + 1;
dp[node][1][0] = temp_dp[1] + 1;
temp_dp[0] = 0;
temp_dp[1] = 1e8;
for (auto u : graph[node]) {
if (u == parent)
continue;
int td0 = temp_dp[0], td1 = temp_dp[1];
temp_dp[0] = min(td1 + dp[u][1][0], td0 + dp[u][0][0]);
temp_dp[1] = min(td1 + dp[u][0][0], td0 + dp[u][1][0]);
}
dp[node][0][0] = temp_dp[0];
dp[node][0][1] = temp_dp[1];
}
void dfs(int node, int parent) {
if (graph[node].size() == 1 && node != 1) {
if (active[node]) {
dp[node][1][0] = 1;
dp[node][0][1] = 0;
dp[node][1][1] = 1e8;
dp[node][0][0] = 1e8;
} else {
dp[node][1][1] = 1;
dp[node][0][0] = 0;
dp[node][1][0] = 1e8;
dp[node][0][1] = 1e8;
}
return ;
}
for (auto u : graph[node]) {
if (u == parent)
continue;
dfs(u, node);
}
if (active[node])
act(node, parent);
else
deact(node, parent);
}
signed main() {
fast
int N, a, b;
cin >> N;
graph = vector<vector<int>>(N+1, vector<int>());
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 2; j++)
for (int q = 0; q < 2; q++)
dp[i][j][q] = 1e8;
}
for (int i = 1; i < N; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= N; i++)
cin >> active[i];
dfs(1, 1);
if (min(dp[1][0][0], dp[1][1][0]) >= 1e8)
cout << "impossible\n";
else
cout << min(dp[1][0][0], dp[1][1][0]) << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
360 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
14428 KB |
Output is correct |
2 |
Correct |
32 ms |
14180 KB |
Output is correct |
3 |
Correct |
39 ms |
14460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
14384 KB |
Output is correct |
2 |
Correct |
32 ms |
14156 KB |
Output is correct |
3 |
Correct |
33 ms |
14424 KB |
Output is correct |
4 |
Correct |
30 ms |
9456 KB |
Output is correct |
5 |
Correct |
32 ms |
10332 KB |
Output is correct |
6 |
Correct |
37 ms |
10588 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
11 ms |
4940 KB |
Output is correct |
9 |
Correct |
35 ms |
11356 KB |
Output is correct |
10 |
Correct |
42 ms |
11604 KB |
Output is correct |
11 |
Correct |
34 ms |
11600 KB |
Output is correct |
12 |
Correct |
35 ms |
11868 KB |
Output is correct |
13 |
Correct |
32 ms |
11580 KB |
Output is correct |
14 |
Correct |
34 ms |
12200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
360 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
33 ms |
14428 KB |
Output is correct |
18 |
Correct |
32 ms |
14180 KB |
Output is correct |
19 |
Correct |
39 ms |
14460 KB |
Output is correct |
20 |
Correct |
32 ms |
14384 KB |
Output is correct |
21 |
Correct |
32 ms |
14156 KB |
Output is correct |
22 |
Correct |
33 ms |
14424 KB |
Output is correct |
23 |
Correct |
30 ms |
9456 KB |
Output is correct |
24 |
Correct |
32 ms |
10332 KB |
Output is correct |
25 |
Correct |
37 ms |
10588 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
11 ms |
4940 KB |
Output is correct |
28 |
Correct |
35 ms |
11356 KB |
Output is correct |
29 |
Correct |
42 ms |
11604 KB |
Output is correct |
30 |
Correct |
34 ms |
11600 KB |
Output is correct |
31 |
Correct |
35 ms |
11868 KB |
Output is correct |
32 |
Correct |
32 ms |
11580 KB |
Output is correct |
33 |
Correct |
34 ms |
12200 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
348 KB |
Output is correct |
44 |
Correct |
0 ms |
348 KB |
Output is correct |
45 |
Correct |
33 ms |
15784 KB |
Output is correct |
46 |
Correct |
33 ms |
15580 KB |
Output is correct |
47 |
Correct |
33 ms |
15892 KB |
Output is correct |
48 |
Correct |
32 ms |
10796 KB |
Output is correct |
49 |
Correct |
40 ms |
11600 KB |
Output is correct |
50 |
Correct |
34 ms |
11868 KB |
Output is correct |
51 |
Correct |
0 ms |
348 KB |
Output is correct |
52 |
Correct |
12 ms |
5212 KB |
Output is correct |
53 |
Correct |
56 ms |
11552 KB |
Output is correct |
54 |
Correct |
38 ms |
11772 KB |
Output is correct |
55 |
Correct |
45 ms |
11696 KB |
Output is correct |
56 |
Correct |
46 ms |
12116 KB |
Output is correct |
57 |
Correct |
41 ms |
11572 KB |
Output is correct |
58 |
Correct |
40 ms |
12248 KB |
Output is correct |
59 |
Correct |
12 ms |
5212 KB |
Output is correct |
60 |
Correct |
31 ms |
10528 KB |
Output is correct |
61 |
Correct |
34 ms |
11348 KB |
Output is correct |
62 |
Correct |
34 ms |
11600 KB |
Output is correct |
63 |
Correct |
35 ms |
11600 KB |
Output is correct |
64 |
Correct |
35 ms |
11612 KB |
Output is correct |
65 |
Correct |
31 ms |
12120 KB |
Output is correct |
66 |
Correct |
32 ms |
12116 KB |
Output is correct |
67 |
Correct |
27 ms |
11976 KB |
Output is correct |
68 |
Correct |
31 ms |
12164 KB |
Output is correct |
69 |
Correct |
37 ms |
11988 KB |
Output is correct |
70 |
Correct |
36 ms |
11980 KB |
Output is correct |