#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
const int INF = 1e9;
vector<int> adj[maxn];
int a[maxn], dp[maxn][2][2];
int n;
void dfs(int pos, int prev){
if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
for(auto x : adj[pos]){
dfs(x, pos);
}
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
//calculate dp[pos][j][k];
vector<int> dif;
int sum = 0;
for(auto x : adj[pos]){
sum += dp[x][0][j];
dif.pb(dp[x][1][j] - dp[x][0][j]);
}
sort(dif.begin(), dif.end());
int nd = (a[pos] + j + k) % 2;
dp[pos][j][k] = INF;
if(nd == 0) dp[pos][j][k] = sum;
for(int i = 0; i < dif.size(); i++){
sum += dif[i];
if((i + 1) % 2 == nd) dp[pos][j][k] = min(dp[pos][j][k], sum);
}
if(j) dp[pos][j][k] += 1;
}
}
}
signed main(void){
fastio;
cin>>n;
for(int i = 0; i < n - 1; i++){
int a, b;
cin>>a>>b;
a--, b--;
adj[a].pb(b);
adj[b].pb(a);
}
for(int i = 0; i < n; i++) cin>>a[i];
dfs(0, -1);
int ans = min(dp[0][0][0], dp[0][1][0]);
if(ans < INF) cout<<ans<<"\n";
else cout<<"impossible\n";
}
Compilation message
xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:35:30: 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]
35 | for(int i = 0; i < dif.size(); i++){
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
8540 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
2 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8700 KB |
Output is correct |
11 |
Correct |
2 ms |
8540 KB |
Output is correct |
12 |
Correct |
2 ms |
8700 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
8540 KB |
Output is correct |
15 |
Correct |
2 ms |
8540 KB |
Output is correct |
16 |
Correct |
2 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
34576 KB |
Output is correct |
2 |
Correct |
61 ms |
34108 KB |
Output is correct |
3 |
Correct |
55 ms |
34464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
34360 KB |
Output is correct |
2 |
Correct |
51 ms |
34064 KB |
Output is correct |
3 |
Correct |
60 ms |
34640 KB |
Output is correct |
4 |
Correct |
46 ms |
17748 KB |
Output is correct |
5 |
Correct |
48 ms |
18004 KB |
Output is correct |
6 |
Correct |
52 ms |
18240 KB |
Output is correct |
7 |
Correct |
2 ms |
8540 KB |
Output is correct |
8 |
Correct |
16 ms |
12728 KB |
Output is correct |
9 |
Correct |
50 ms |
17916 KB |
Output is correct |
10 |
Correct |
64 ms |
18004 KB |
Output is correct |
11 |
Correct |
62 ms |
19252 KB |
Output is correct |
12 |
Correct |
60 ms |
19500 KB |
Output is correct |
13 |
Correct |
45 ms |
18264 KB |
Output is correct |
14 |
Correct |
67 ms |
18768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
8540 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
2 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8700 KB |
Output is correct |
11 |
Correct |
2 ms |
8540 KB |
Output is correct |
12 |
Correct |
2 ms |
8700 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
8540 KB |
Output is correct |
15 |
Correct |
2 ms |
8540 KB |
Output is correct |
16 |
Correct |
2 ms |
8540 KB |
Output is correct |
17 |
Correct |
66 ms |
34576 KB |
Output is correct |
18 |
Correct |
61 ms |
34108 KB |
Output is correct |
19 |
Correct |
55 ms |
34464 KB |
Output is correct |
20 |
Correct |
53 ms |
34360 KB |
Output is correct |
21 |
Correct |
51 ms |
34064 KB |
Output is correct |
22 |
Correct |
60 ms |
34640 KB |
Output is correct |
23 |
Correct |
46 ms |
17748 KB |
Output is correct |
24 |
Correct |
48 ms |
18004 KB |
Output is correct |
25 |
Correct |
52 ms |
18240 KB |
Output is correct |
26 |
Correct |
2 ms |
8540 KB |
Output is correct |
27 |
Correct |
16 ms |
12728 KB |
Output is correct |
28 |
Correct |
50 ms |
17916 KB |
Output is correct |
29 |
Correct |
64 ms |
18004 KB |
Output is correct |
30 |
Correct |
62 ms |
19252 KB |
Output is correct |
31 |
Correct |
60 ms |
19500 KB |
Output is correct |
32 |
Correct |
45 ms |
18264 KB |
Output is correct |
33 |
Correct |
67 ms |
18768 KB |
Output is correct |
34 |
Correct |
2 ms |
8540 KB |
Output is correct |
35 |
Correct |
2 ms |
8540 KB |
Output is correct |
36 |
Correct |
2 ms |
8540 KB |
Output is correct |
37 |
Correct |
2 ms |
8540 KB |
Output is correct |
38 |
Correct |
1 ms |
8540 KB |
Output is correct |
39 |
Correct |
2 ms |
8540 KB |
Output is correct |
40 |
Correct |
2 ms |
8700 KB |
Output is correct |
41 |
Correct |
2 ms |
8540 KB |
Output is correct |
42 |
Correct |
2 ms |
8540 KB |
Output is correct |
43 |
Correct |
2 ms |
8540 KB |
Output is correct |
44 |
Correct |
2 ms |
8540 KB |
Output is correct |
45 |
Correct |
68 ms |
34388 KB |
Output is correct |
46 |
Correct |
55 ms |
34244 KB |
Output is correct |
47 |
Correct |
54 ms |
34472 KB |
Output is correct |
48 |
Correct |
51 ms |
17576 KB |
Output is correct |
49 |
Correct |
66 ms |
18000 KB |
Output is correct |
50 |
Correct |
68 ms |
18328 KB |
Output is correct |
51 |
Correct |
2 ms |
8540 KB |
Output is correct |
52 |
Correct |
16 ms |
12640 KB |
Output is correct |
53 |
Correct |
49 ms |
18012 KB |
Output is correct |
54 |
Correct |
68 ms |
18200 KB |
Output is correct |
55 |
Correct |
49 ms |
19228 KB |
Output is correct |
56 |
Correct |
60 ms |
19504 KB |
Output is correct |
57 |
Correct |
45 ms |
18256 KB |
Output is correct |
58 |
Correct |
48 ms |
18376 KB |
Output is correct |
59 |
Correct |
16 ms |
12376 KB |
Output is correct |
60 |
Correct |
51 ms |
17492 KB |
Output is correct |
61 |
Correct |
58 ms |
17908 KB |
Output is correct |
62 |
Correct |
73 ms |
18408 KB |
Output is correct |
63 |
Correct |
49 ms |
18100 KB |
Output is correct |
64 |
Correct |
57 ms |
18004 KB |
Output is correct |
65 |
Correct |
55 ms |
18260 KB |
Output is correct |
66 |
Correct |
44 ms |
18264 KB |
Output is correct |
67 |
Correct |
38 ms |
20028 KB |
Output is correct |
68 |
Correct |
38 ms |
20020 KB |
Output is correct |
69 |
Correct |
44 ms |
19976 KB |
Output is correct |
70 |
Correct |
42 ms |
20024 KB |
Output is correct |