#include <iostream>
#include <vector>
using namespace std;
/*
dp[u][flag1][flag2] = minimum toggles from descendants of u only required such that:
state of u is flag1
state of all direct children of u is flag2
state of all other descendants is 0.
if this is impossible, 1e9;
*/
vector<int> edge[100001];
int sv[100001];
vector<int> p(100001, 0);
vector<int> children[100001];
int dp[100001][2][2];
void dfs1(int u)
{
for(int v: edge[u])
{
if(p[u] == v) continue;
p[v] = u;
children[u].push_back(v);
dfs1(v);
}
}
void dfs2(int u)
{
for(int v: children[u])
dfs2(v);
dp[u][ sv[u] ][0] = dp[u][ sv[u] ][1] = 0;
//dp_curr[u][flag1][flag2] = state of dp assuming it has only previously visited children
for(int v: children[u])
{
int X[2][2];
for(int f = 0; f <= 1; f++)
for(int g = 0; g <= 1; g++)
X[f][g] = min(dp[u][f][g] + dp[v][g][0], dp[u][!f][g] + dp[v][!g][1] + 1);
for(int f = 0; f <= 1; f++)
for(int g = 0; g <= 1; g++)
dp[u][f][g] = X[f][g];
}
// cout << u << ' ' << dp[u][0][0] << ' ' << dp[u][0][1] << ' ' << dp[u][1][0] << ' ' << dp[u][1][1] << '\n';
}
int main()
{
int N;
cin >> N;
for(int i = 1; i <= N-1; i++)
{
int a, b;
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
edge[1].push_back(0);
edge[0].push_back(1);
dfs1(0);
for(int i = 0; i <= N; i++)
{
for(int f = 0; f <= 1; f++)
for(int g = 0; g <= 1; g++)
dp[i][f][g] = N+1;
}
for(int i = 1; i <= N; i++)
cin >> sv[i];
dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = 0;
dfs2(0);
int res = min(dp[0][0][0], dp[0][1][0]);
if(res >= N+1) cout << "impossible\n";
else cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5324 KB |
Output is correct |
2 |
Correct |
4 ms |
5452 KB |
Output is correct |
3 |
Correct |
3 ms |
5408 KB |
Output is correct |
4 |
Correct |
4 ms |
5324 KB |
Output is correct |
5 |
Correct |
10 ms |
5324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5324 KB |
Output is correct |
2 |
Correct |
4 ms |
5452 KB |
Output is correct |
3 |
Correct |
3 ms |
5408 KB |
Output is correct |
4 |
Correct |
4 ms |
5324 KB |
Output is correct |
5 |
Correct |
10 ms |
5324 KB |
Output is correct |
6 |
Correct |
3 ms |
5324 KB |
Output is correct |
7 |
Correct |
4 ms |
5324 KB |
Output is correct |
8 |
Correct |
3 ms |
5324 KB |
Output is correct |
9 |
Correct |
3 ms |
5324 KB |
Output is correct |
10 |
Correct |
3 ms |
5416 KB |
Output is correct |
11 |
Correct |
4 ms |
5324 KB |
Output is correct |
12 |
Correct |
4 ms |
5412 KB |
Output is correct |
13 |
Correct |
4 ms |
5324 KB |
Output is correct |
14 |
Correct |
3 ms |
5324 KB |
Output is correct |
15 |
Correct |
3 ms |
5404 KB |
Output is correct |
16 |
Correct |
3 ms |
5408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
22568 KB |
Output is correct |
2 |
Correct |
138 ms |
22656 KB |
Output is correct |
3 |
Correct |
133 ms |
22680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
22596 KB |
Output is correct |
2 |
Correct |
121 ms |
22476 KB |
Output is correct |
3 |
Correct |
147 ms |
22716 KB |
Output is correct |
4 |
Correct |
114 ms |
12784 KB |
Output is correct |
5 |
Correct |
137 ms |
13568 KB |
Output is correct |
6 |
Correct |
147 ms |
13664 KB |
Output is correct |
7 |
Correct |
4 ms |
5324 KB |
Output is correct |
8 |
Correct |
43 ms |
8288 KB |
Output is correct |
9 |
Correct |
136 ms |
14088 KB |
Output is correct |
10 |
Correct |
148 ms |
14124 KB |
Output is correct |
11 |
Correct |
151 ms |
14580 KB |
Output is correct |
12 |
Correct |
152 ms |
14932 KB |
Output is correct |
13 |
Correct |
117 ms |
12808 KB |
Output is correct |
14 |
Correct |
159 ms |
13272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5324 KB |
Output is correct |
2 |
Correct |
4 ms |
5452 KB |
Output is correct |
3 |
Correct |
3 ms |
5408 KB |
Output is correct |
4 |
Correct |
4 ms |
5324 KB |
Output is correct |
5 |
Correct |
10 ms |
5324 KB |
Output is correct |
6 |
Correct |
3 ms |
5324 KB |
Output is correct |
7 |
Correct |
4 ms |
5324 KB |
Output is correct |
8 |
Correct |
3 ms |
5324 KB |
Output is correct |
9 |
Correct |
3 ms |
5324 KB |
Output is correct |
10 |
Correct |
3 ms |
5416 KB |
Output is correct |
11 |
Correct |
4 ms |
5324 KB |
Output is correct |
12 |
Correct |
4 ms |
5412 KB |
Output is correct |
13 |
Correct |
4 ms |
5324 KB |
Output is correct |
14 |
Correct |
3 ms |
5324 KB |
Output is correct |
15 |
Correct |
3 ms |
5404 KB |
Output is correct |
16 |
Correct |
3 ms |
5408 KB |
Output is correct |
17 |
Correct |
127 ms |
22568 KB |
Output is correct |
18 |
Correct |
138 ms |
22656 KB |
Output is correct |
19 |
Correct |
133 ms |
22680 KB |
Output is correct |
20 |
Correct |
126 ms |
22596 KB |
Output is correct |
21 |
Correct |
121 ms |
22476 KB |
Output is correct |
22 |
Correct |
147 ms |
22716 KB |
Output is correct |
23 |
Correct |
114 ms |
12784 KB |
Output is correct |
24 |
Correct |
137 ms |
13568 KB |
Output is correct |
25 |
Correct |
147 ms |
13664 KB |
Output is correct |
26 |
Correct |
4 ms |
5324 KB |
Output is correct |
27 |
Correct |
43 ms |
8288 KB |
Output is correct |
28 |
Correct |
136 ms |
14088 KB |
Output is correct |
29 |
Correct |
148 ms |
14124 KB |
Output is correct |
30 |
Correct |
151 ms |
14580 KB |
Output is correct |
31 |
Correct |
152 ms |
14932 KB |
Output is correct |
32 |
Correct |
117 ms |
12808 KB |
Output is correct |
33 |
Correct |
159 ms |
13272 KB |
Output is correct |
34 |
Correct |
3 ms |
5324 KB |
Output is correct |
35 |
Correct |
3 ms |
5404 KB |
Output is correct |
36 |
Correct |
4 ms |
5400 KB |
Output is correct |
37 |
Correct |
3 ms |
5324 KB |
Output is correct |
38 |
Correct |
4 ms |
5408 KB |
Output is correct |
39 |
Correct |
4 ms |
5324 KB |
Output is correct |
40 |
Correct |
4 ms |
5324 KB |
Output is correct |
41 |
Correct |
4 ms |
5324 KB |
Output is correct |
42 |
Correct |
3 ms |
5324 KB |
Output is correct |
43 |
Correct |
4 ms |
5324 KB |
Output is correct |
44 |
Correct |
3 ms |
5404 KB |
Output is correct |
45 |
Correct |
122 ms |
22596 KB |
Output is correct |
46 |
Correct |
129 ms |
22404 KB |
Output is correct |
47 |
Correct |
130 ms |
22708 KB |
Output is correct |
48 |
Correct |
117 ms |
12856 KB |
Output is correct |
49 |
Correct |
134 ms |
13508 KB |
Output is correct |
50 |
Correct |
141 ms |
13692 KB |
Output is correct |
51 |
Correct |
4 ms |
5324 KB |
Output is correct |
52 |
Correct |
42 ms |
8308 KB |
Output is correct |
53 |
Correct |
147 ms |
14072 KB |
Output is correct |
54 |
Correct |
132 ms |
14148 KB |
Output is correct |
55 |
Correct |
139 ms |
14688 KB |
Output is correct |
56 |
Correct |
154 ms |
14860 KB |
Output is correct |
57 |
Correct |
136 ms |
12868 KB |
Output is correct |
58 |
Correct |
131 ms |
13364 KB |
Output is correct |
59 |
Correct |
41 ms |
8132 KB |
Output is correct |
60 |
Correct |
124 ms |
12876 KB |
Output is correct |
61 |
Correct |
131 ms |
13696 KB |
Output is correct |
62 |
Correct |
178 ms |
13824 KB |
Output is correct |
63 |
Correct |
133 ms |
13832 KB |
Output is correct |
64 |
Correct |
139 ms |
13880 KB |
Output is correct |
65 |
Correct |
129 ms |
12856 KB |
Output is correct |
66 |
Correct |
127 ms |
12800 KB |
Output is correct |
67 |
Correct |
107 ms |
12636 KB |
Output is correct |
68 |
Correct |
107 ms |
12736 KB |
Output is correct |
69 |
Correct |
108 ms |
12736 KB |
Output is correct |
70 |
Correct |
110 ms |
12724 KB |
Output is correct |