#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, INF=1e9+7;
vector<int>V[LIM];
int dp[LIM][2][2], T[LIM];
void DFS(int x, int o) {
int dp2[2][2];
dp2[0][0]=dp2[0][1]=0;
dp2[1][0]=dp2[1][1]=INF;
for(auto i : V[x]) if(i!=o) {
DFS(i, x);
int dp3[2][2];
rep(a, 2) rep(b, 2) dp3[a][b]=INF;
rep(a, 2) {
dp3[0][a]=min(dp3[0][a], dp2[0][a]+dp[i][0][a]);
dp3[0][a]=min(dp3[0][a], dp2[1][a]+dp[i][1][a]);
dp3[1][a]=min(dp3[1][a], dp2[0][a]+dp[i][1][a]);
dp3[1][a]=min(dp3[1][a], dp2[1][a]+dp[i][0][a]);
}
rep(a, 2) rep(b, 2) dp2[a][b]=dp3[a][b];
}
rep(i, 2) {
dp[x][0][i]=min(dp2[i^T[x]][0], INF);
dp[x][1][i]=min(dp2[i^T[x]^1][1]+1, INF);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
rep(i, n-1) {
int a, b;
cin >> a >> b; --a; --b;
V[a].pb(b);
V[b].pb(a);
}
rep(i, n) cin >> T[i];
DFS(0, 0);
if(min(dp[0][0][0], dp[0][1][0])==INF) cout << "impossible\n";
else cout << min(dp[0][0][0], dp[0][1][0]) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2676 KB |
Output is correct |
6 |
Correct |
2 ms |
2676 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2680 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
18392 KB |
Output is correct |
2 |
Correct |
48 ms |
18160 KB |
Output is correct |
3 |
Correct |
47 ms |
18356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
18424 KB |
Output is correct |
2 |
Correct |
59 ms |
18212 KB |
Output is correct |
3 |
Correct |
70 ms |
18380 KB |
Output is correct |
4 |
Correct |
54 ms |
8372 KB |
Output is correct |
5 |
Correct |
52 ms |
8956 KB |
Output is correct |
6 |
Correct |
48 ms |
8968 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
15 ms |
4820 KB |
Output is correct |
9 |
Correct |
58 ms |
9116 KB |
Output is correct |
10 |
Correct |
70 ms |
9204 KB |
Output is correct |
11 |
Correct |
71 ms |
9612 KB |
Output is correct |
12 |
Correct |
52 ms |
9932 KB |
Output is correct |
13 |
Correct |
44 ms |
8588 KB |
Output is correct |
14 |
Correct |
48 ms |
9064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2676 KB |
Output is correct |
6 |
Correct |
2 ms |
2676 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2680 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2676 KB |
Output is correct |
17 |
Correct |
75 ms |
18392 KB |
Output is correct |
18 |
Correct |
48 ms |
18160 KB |
Output is correct |
19 |
Correct |
47 ms |
18356 KB |
Output is correct |
20 |
Correct |
53 ms |
18424 KB |
Output is correct |
21 |
Correct |
59 ms |
18212 KB |
Output is correct |
22 |
Correct |
70 ms |
18380 KB |
Output is correct |
23 |
Correct |
54 ms |
8372 KB |
Output is correct |
24 |
Correct |
52 ms |
8956 KB |
Output is correct |
25 |
Correct |
48 ms |
8968 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
15 ms |
4820 KB |
Output is correct |
28 |
Correct |
58 ms |
9116 KB |
Output is correct |
29 |
Correct |
70 ms |
9204 KB |
Output is correct |
30 |
Correct |
71 ms |
9612 KB |
Output is correct |
31 |
Correct |
52 ms |
9932 KB |
Output is correct |
32 |
Correct |
44 ms |
8588 KB |
Output is correct |
33 |
Correct |
48 ms |
9064 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
2 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2644 KB |
Output is correct |
39 |
Correct |
2 ms |
2592 KB |
Output is correct |
40 |
Correct |
1 ms |
2680 KB |
Output is correct |
41 |
Correct |
2 ms |
2644 KB |
Output is correct |
42 |
Correct |
2 ms |
2672 KB |
Output is correct |
43 |
Correct |
2 ms |
2644 KB |
Output is correct |
44 |
Correct |
2 ms |
2644 KB |
Output is correct |
45 |
Correct |
54 ms |
18396 KB |
Output is correct |
46 |
Correct |
51 ms |
18172 KB |
Output is correct |
47 |
Correct |
60 ms |
18388 KB |
Output is correct |
48 |
Correct |
69 ms |
8400 KB |
Output is correct |
49 |
Correct |
49 ms |
8840 KB |
Output is correct |
50 |
Correct |
52 ms |
9072 KB |
Output is correct |
51 |
Correct |
2 ms |
2644 KB |
Output is correct |
52 |
Correct |
15 ms |
4756 KB |
Output is correct |
53 |
Correct |
48 ms |
8992 KB |
Output is correct |
54 |
Correct |
54 ms |
9284 KB |
Output is correct |
55 |
Correct |
71 ms |
9712 KB |
Output is correct |
56 |
Correct |
62 ms |
9852 KB |
Output is correct |
57 |
Correct |
44 ms |
8588 KB |
Output is correct |
58 |
Correct |
50 ms |
9060 KB |
Output is correct |
59 |
Correct |
21 ms |
4748 KB |
Output is correct |
60 |
Correct |
60 ms |
8528 KB |
Output is correct |
61 |
Correct |
63 ms |
8944 KB |
Output is correct |
62 |
Correct |
47 ms |
9132 KB |
Output is correct |
63 |
Correct |
47 ms |
9084 KB |
Output is correct |
64 |
Correct |
56 ms |
9088 KB |
Output is correct |
65 |
Correct |
49 ms |
9640 KB |
Output is correct |
66 |
Correct |
51 ms |
9520 KB |
Output is correct |
67 |
Correct |
49 ms |
9452 KB |
Output is correct |
68 |
Correct |
34 ms |
9456 KB |
Output is correct |
69 |
Correct |
37 ms |
9512 KB |
Output is correct |
70 |
Correct |
34 ms |
9504 KB |
Output is correct |