#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=1e5+5,INF=1e9;
int n,c[MAX],f[MAX][2][2];
vector<int> g[MAX];
void dfs(int u,int p) {
for(int v:g[u]) {
if(v==p)
continue;
dfs(v,u);
}
// Not toggle u
int sum=0,change=0;
vector<int> V;
for(int v:g[u]) {
if(v==p)
continue;
sum+=f[v][0][0];
V.push_back(f[v][1][0]-f[v][0][0]);
}
if(V.size()==0) {
f[u][0][c[u]]=0;
f[u][1][c[u]^1]=1;
return;
}
sort(V.begin(),V.end());
for(int i=0;i<=V.size();i++) {
if((i+c[u])%2==0)
f[u][0][0]=min(f[u][0][0],sum+change);
else
f[u][0][1]=min(f[u][0][1],sum+change);
if(i<V.size())
change+=V[i];
}
// Toggle u
sum=change=0;
V.clear();
for(int v:g[u]) {
if(v==p)
continue;
sum+=f[v][0][1];
V.push_back(f[v][1][1]-f[v][0][1]);
}
sort(V.begin(),V.end());
for(int i=0;i<=V.size();i++) {
if((i+c[u])%2==0)
f[u][1][1]=min(f[u][1][1],sum+change+1);
else
f[u][1][0]=min(f[u][1][0],sum+change+1);
if(i<V.size())
change+=V[i];
}
}
int32_t main() {
#ifdef ACM
freopen("input","r",stdin);
#endif
cin>>n;
int u,v;
for(int i=1;i<n;i++) {
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
f[i][0][0]=f[i][0][1]=f[i][1][0]=f[i][1][1]=INF;
dfs(1,1);
int rs=min(f[1][0][0],f[1][1][0]);
if(rs==INF)
cout<<"impossible";
else
cout<<rs;
}
Compilation message
xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:30:15: 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]
30 | for(int i=0;i<=V.size();i++) {
| ~^~~~~~~~~~
xanadu.cpp:35:7: 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 | if(i<V.size())
| ~^~~~~~~~~
xanadu.cpp:48:15: 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]
48 | for(int i=0;i<=V.size();i++) {
| ~^~~~~~~~~~
xanadu.cpp:53:7: 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]
53 | if(i<V.size())
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2636 KB |
Output is correct |
8 |
Correct |
3 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2648 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
23356 KB |
Output is correct |
2 |
Correct |
169 ms |
23068 KB |
Output is correct |
3 |
Correct |
156 ms |
23492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
23364 KB |
Output is correct |
2 |
Correct |
143 ms |
23108 KB |
Output is correct |
3 |
Correct |
185 ms |
23520 KB |
Output is correct |
4 |
Correct |
126 ms |
10852 KB |
Output is correct |
5 |
Correct |
152 ms |
11648 KB |
Output is correct |
6 |
Correct |
154 ms |
11800 KB |
Output is correct |
7 |
Correct |
3 ms |
2636 KB |
Output is correct |
8 |
Correct |
47 ms |
5676 KB |
Output is correct |
9 |
Correct |
156 ms |
11432 KB |
Output is correct |
10 |
Correct |
146 ms |
11588 KB |
Output is correct |
11 |
Correct |
144 ms |
12264 KB |
Output is correct |
12 |
Correct |
169 ms |
12644 KB |
Output is correct |
13 |
Correct |
180 ms |
11476 KB |
Output is correct |
14 |
Correct |
154 ms |
12068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2636 KB |
Output is correct |
8 |
Correct |
3 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2648 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
154 ms |
23356 KB |
Output is correct |
18 |
Correct |
169 ms |
23068 KB |
Output is correct |
19 |
Correct |
156 ms |
23492 KB |
Output is correct |
20 |
Correct |
132 ms |
23364 KB |
Output is correct |
21 |
Correct |
143 ms |
23108 KB |
Output is correct |
22 |
Correct |
185 ms |
23520 KB |
Output is correct |
23 |
Correct |
126 ms |
10852 KB |
Output is correct |
24 |
Correct |
152 ms |
11648 KB |
Output is correct |
25 |
Correct |
154 ms |
11800 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
47 ms |
5676 KB |
Output is correct |
28 |
Correct |
156 ms |
11432 KB |
Output is correct |
29 |
Correct |
146 ms |
11588 KB |
Output is correct |
30 |
Correct |
144 ms |
12264 KB |
Output is correct |
31 |
Correct |
169 ms |
12644 KB |
Output is correct |
32 |
Correct |
180 ms |
11476 KB |
Output is correct |
33 |
Correct |
154 ms |
12068 KB |
Output is correct |
34 |
Correct |
2 ms |
2764 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
3 ms |
2656 KB |
Output is correct |
39 |
Correct |
3 ms |
2636 KB |
Output is correct |
40 |
Correct |
2 ms |
2636 KB |
Output is correct |
41 |
Correct |
2 ms |
2636 KB |
Output is correct |
42 |
Correct |
2 ms |
2624 KB |
Output is correct |
43 |
Correct |
2 ms |
2636 KB |
Output is correct |
44 |
Correct |
2 ms |
2636 KB |
Output is correct |
45 |
Correct |
149 ms |
23448 KB |
Output is correct |
46 |
Correct |
152 ms |
23136 KB |
Output is correct |
47 |
Correct |
155 ms |
23492 KB |
Output is correct |
48 |
Correct |
158 ms |
10860 KB |
Output is correct |
49 |
Correct |
165 ms |
11664 KB |
Output is correct |
50 |
Correct |
173 ms |
12104 KB |
Output is correct |
51 |
Correct |
3 ms |
2636 KB |
Output is correct |
52 |
Correct |
40 ms |
5620 KB |
Output is correct |
53 |
Correct |
173 ms |
11504 KB |
Output is correct |
54 |
Correct |
158 ms |
11628 KB |
Output is correct |
55 |
Correct |
172 ms |
12240 KB |
Output is correct |
56 |
Correct |
198 ms |
12612 KB |
Output is correct |
57 |
Correct |
157 ms |
11588 KB |
Output is correct |
58 |
Correct |
159 ms |
12172 KB |
Output is correct |
59 |
Correct |
43 ms |
5572 KB |
Output is correct |
60 |
Correct |
147 ms |
10616 KB |
Output is correct |
61 |
Correct |
137 ms |
11384 KB |
Output is correct |
62 |
Correct |
169 ms |
11784 KB |
Output is correct |
63 |
Correct |
148 ms |
11604 KB |
Output is correct |
64 |
Correct |
157 ms |
11596 KB |
Output is correct |
65 |
Correct |
142 ms |
12136 KB |
Output is correct |
66 |
Correct |
134 ms |
12064 KB |
Output is correct |
67 |
Correct |
118 ms |
13292 KB |
Output is correct |
68 |
Correct |
115 ms |
13340 KB |
Output is correct |
69 |
Correct |
127 ms |
13348 KB |
Output is correct |
70 |
Correct |
139 ms |
13352 KB |
Output is correct |