#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5;
int n, r[N];
ll a[N], b[N], c[N], d[N];
vector<int>g[N];
void dfs(const int &v, const int &p=-1){
b[v]=d[v]=1;
vector<int>x, y;
for(int u: g[v]){
if(u!=p){
dfs(u, v);
a[v]+=a[u];
c[v]+=a[u];
x.push_back(b[u]-a[u]);
b[v]+=c[u];
d[v]+=c[u];
y.push_back(d[u]-c[u]);
}
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
ll aa=1e18, bb=1e18, cc=1e18, dd=1e18;
if(r[v]){
aa=0;
dd=0;
}
else{
bb=0;
cc=0;
}
ll sm=0;
bool h=r[v];
for(int u: x){
sm+=u;
if(h)
cc=min(cc, sm);
else
aa=min(aa, sm);
h=!h;
}
h=r[v];
sm=0;
for(int u: y){
sm+=u;
if(h)
bb=min(bb, sm);
else
dd=min(dd, sm);
h=!h;
}
a[v]+=aa;
b[v]+=bb;
c[v]+=cc;
d[v]+=dd;
ll zz=1e9;
a[v]=min(a[v], zz);
b[v]=min(b[v], zz);
c[v]=min(c[v], zz);
d[v]=min(d[v], zz);
}
int main(){
cin>>n;
for(int i=1;i<n;++i){
int u, v;
cin>>u>>v;
g[--u].push_back(--v);
g[v].push_back(u);
}
for(int i=0;i<n;++i){
cin>>r[i];
r[i]=1-r[i];
}
dfs(0);
int z=min(a[0], b[0]);
if(z>n)
cout<<"impossible\n";
else
cout<<z<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 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 |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
26304 KB |
Output is correct |
2 |
Correct |
105 ms |
26036 KB |
Output is correct |
3 |
Correct |
106 ms |
26460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
26316 KB |
Output is correct |
2 |
Correct |
103 ms |
26112 KB |
Output is correct |
3 |
Correct |
135 ms |
26536 KB |
Output is correct |
4 |
Correct |
105 ms |
8592 KB |
Output is correct |
5 |
Correct |
105 ms |
9160 KB |
Output is correct |
6 |
Correct |
119 ms |
9328 KB |
Output is correct |
7 |
Correct |
2 ms |
2620 KB |
Output is correct |
8 |
Correct |
43 ms |
4996 KB |
Output is correct |
9 |
Correct |
123 ms |
9336 KB |
Output is correct |
10 |
Correct |
111 ms |
9448 KB |
Output is correct |
11 |
Correct |
110 ms |
10732 KB |
Output is correct |
12 |
Correct |
116 ms |
11132 KB |
Output is correct |
13 |
Correct |
95 ms |
8840 KB |
Output is correct |
14 |
Correct |
100 ms |
9292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 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 |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
107 ms |
26304 KB |
Output is correct |
18 |
Correct |
105 ms |
26036 KB |
Output is correct |
19 |
Correct |
106 ms |
26460 KB |
Output is correct |
20 |
Correct |
110 ms |
26316 KB |
Output is correct |
21 |
Correct |
103 ms |
26112 KB |
Output is correct |
22 |
Correct |
135 ms |
26536 KB |
Output is correct |
23 |
Correct |
105 ms |
8592 KB |
Output is correct |
24 |
Correct |
105 ms |
9160 KB |
Output is correct |
25 |
Correct |
119 ms |
9328 KB |
Output is correct |
26 |
Correct |
2 ms |
2620 KB |
Output is correct |
27 |
Correct |
43 ms |
4996 KB |
Output is correct |
28 |
Correct |
123 ms |
9336 KB |
Output is correct |
29 |
Correct |
111 ms |
9448 KB |
Output is correct |
30 |
Correct |
110 ms |
10732 KB |
Output is correct |
31 |
Correct |
116 ms |
11132 KB |
Output is correct |
32 |
Correct |
95 ms |
8840 KB |
Output is correct |
33 |
Correct |
100 ms |
9292 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
1 ms |
2644 KB |
Output is correct |
36 |
Correct |
1 ms |
2644 KB |
Output is correct |
37 |
Correct |
1 ms |
2644 KB |
Output is correct |
38 |
Correct |
1 ms |
2644 KB |
Output is correct |
39 |
Correct |
2 ms |
2644 KB |
Output is correct |
40 |
Correct |
1 ms |
2644 KB |
Output is correct |
41 |
Correct |
2 ms |
2644 KB |
Output is correct |
42 |
Correct |
1 ms |
2644 KB |
Output is correct |
43 |
Correct |
1 ms |
2644 KB |
Output is correct |
44 |
Correct |
2 ms |
2644 KB |
Output is correct |
45 |
Correct |
111 ms |
26372 KB |
Output is correct |
46 |
Correct |
111 ms |
26160 KB |
Output is correct |
47 |
Correct |
102 ms |
26472 KB |
Output is correct |
48 |
Correct |
108 ms |
8588 KB |
Output is correct |
49 |
Correct |
104 ms |
9180 KB |
Output is correct |
50 |
Correct |
122 ms |
9356 KB |
Output is correct |
51 |
Correct |
2 ms |
2644 KB |
Output is correct |
52 |
Correct |
34 ms |
4992 KB |
Output is correct |
53 |
Correct |
109 ms |
9368 KB |
Output is correct |
54 |
Correct |
113 ms |
9548 KB |
Output is correct |
55 |
Correct |
115 ms |
10824 KB |
Output is correct |
56 |
Correct |
115 ms |
11072 KB |
Output is correct |
57 |
Correct |
94 ms |
8892 KB |
Output is correct |
58 |
Correct |
102 ms |
9284 KB |
Output is correct |
59 |
Correct |
30 ms |
4936 KB |
Output is correct |
60 |
Correct |
89 ms |
8616 KB |
Output is correct |
61 |
Correct |
111 ms |
9260 KB |
Output is correct |
62 |
Correct |
124 ms |
9424 KB |
Output is correct |
63 |
Correct |
113 ms |
9380 KB |
Output is correct |
64 |
Correct |
99 ms |
9420 KB |
Output is correct |
65 |
Correct |
90 ms |
9788 KB |
Output is correct |
66 |
Correct |
91 ms |
9808 KB |
Output is correct |
67 |
Correct |
92 ms |
10824 KB |
Output is correct |
68 |
Correct |
85 ms |
10820 KB |
Output is correct |
69 |
Correct |
84 ms |
10828 KB |
Output is correct |
70 |
Correct |
83 ms |
10900 KB |
Output is correct |