#include <bits/stdc++.h>
using namespace std;
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
typedef pair<long double,long long> pdl;
const ll base=361;
const ll mod=1e9;
const ll mod2=1e9;
const ld eps=1e-3;
const ld eps2=1e-7;
const ll maxn=1e6+9;
const ll maxsize=6e5+29;
const ld pi=acos(-1);
//const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const int dxkn[8]={1,1,2,2,-1,-1,-2,-2};
const int dykn[8]={2,-2,1,-1,2,-2,1,-1};
const int dxki[8]={1,1,1,0,0,-1,-1,-1};
const int dyki[8]={1,0,-1,1,-1,1,0,-1};
int n,i,u,v,f[200009][3][3],newf[200009][3][3],a[200009],j,ans;
vector<int> g[200009];
void dfs(int x,int y) {
if (a[x]==0) {
f[x][0][0]=0;
f[x][0][1]=oo;
f[x][1][0]=oo;
f[x][1][1]=1;
}
else {
f[x][0][0]=oo;
f[x][0][1]=1;
f[x][1][0]=0;
f[x][1][1]=oo;
}
for (int ii:g[x]) {
if (ii!=y) {
dfs(ii,x);
newf[x][0][0]=min(f[x][0][0]+f[ii][0][0],f[x][1][0]+f[ii][0][1]);
newf[x][0][1]=min(f[x][0][1]+f[ii][1][0],f[x][1][1]+f[ii][1][1]);
newf[x][1][0]=min(f[x][1][0]+f[ii][0][0],f[x][0][0]+f[ii][0][1]);
newf[x][1][1]=min(f[x][1][1]+f[ii][1][0],f[x][0][1]+f[ii][1][1]);
f[x][0][0]=newf[x][0][0];
f[x][0][1]=newf[x][0][1];
f[x][1][0]=newf[x][1][0];
f[x][1][1]=newf[x][1][1];
f[x][0][0]=min(f[x][0][0],int(oo));
f[x][0][1]=min(f[x][0][1],int(oo));
f[x][1][0]=min(f[x][1][0],int(oo));
f[x][1][1]=min(f[x][1][1],int(oo));
}
}
f[x][0][0]=min(f[x][0][0],int(oo));
f[x][0][1]=min(f[x][0][1],int(oo));
f[x][1][0]=min(f[x][1][0],int(oo));
f[x][1][1]=min(f[x][1][1],int(oo));
}
int main() {
IO;
cin>>n;
for (i=1;i<n;i++) {
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (i=1;i<=n;i++) {
cin>>a[i];
}
dfs(1,1);
//for (i=1;i<=n;i++) {
//cout<<f[i][0][0]<<' '<<f[i][0][1]<<' '<<f[i][1][0]<<' '<<f[i][1][1]<<'\n';
//}
ans=min({f[1][0][0],f[1][0][1]});
if (ans>=2*n+1) {
cout<<"impossible\n";
return 0;
}
else {
cout<<ans<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
5012 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
4 ms |
5020 KB |
Output is correct |
15 |
Correct |
3 ms |
5020 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
25040 KB |
Output is correct |
2 |
Correct |
75 ms |
24772 KB |
Output is correct |
3 |
Correct |
88 ms |
25136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
25028 KB |
Output is correct |
2 |
Correct |
71 ms |
24860 KB |
Output is correct |
3 |
Correct |
72 ms |
25164 KB |
Output is correct |
4 |
Correct |
64 ms |
14584 KB |
Output is correct |
5 |
Correct |
71 ms |
15560 KB |
Output is correct |
6 |
Correct |
72 ms |
16916 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
23 ms |
8948 KB |
Output is correct |
9 |
Correct |
81 ms |
16808 KB |
Output is correct |
10 |
Correct |
93 ms |
16936 KB |
Output is correct |
11 |
Correct |
73 ms |
17288 KB |
Output is correct |
12 |
Correct |
86 ms |
17748 KB |
Output is correct |
13 |
Correct |
65 ms |
16064 KB |
Output is correct |
14 |
Correct |
82 ms |
16892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
5012 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
4 ms |
5020 KB |
Output is correct |
15 |
Correct |
3 ms |
5020 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
69 ms |
25040 KB |
Output is correct |
18 |
Correct |
75 ms |
24772 KB |
Output is correct |
19 |
Correct |
88 ms |
25136 KB |
Output is correct |
20 |
Correct |
64 ms |
25028 KB |
Output is correct |
21 |
Correct |
71 ms |
24860 KB |
Output is correct |
22 |
Correct |
72 ms |
25164 KB |
Output is correct |
23 |
Correct |
64 ms |
14584 KB |
Output is correct |
24 |
Correct |
71 ms |
15560 KB |
Output is correct |
25 |
Correct |
72 ms |
16916 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
23 ms |
8948 KB |
Output is correct |
28 |
Correct |
81 ms |
16808 KB |
Output is correct |
29 |
Correct |
93 ms |
16936 KB |
Output is correct |
30 |
Correct |
73 ms |
17288 KB |
Output is correct |
31 |
Correct |
86 ms |
17748 KB |
Output is correct |
32 |
Correct |
65 ms |
16064 KB |
Output is correct |
33 |
Correct |
82 ms |
16892 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4968 KB |
Output is correct |
36 |
Correct |
3 ms |
5020 KB |
Output is correct |
37 |
Correct |
3 ms |
5016 KB |
Output is correct |
38 |
Correct |
3 ms |
4940 KB |
Output is correct |
39 |
Correct |
3 ms |
4940 KB |
Output is correct |
40 |
Correct |
3 ms |
5016 KB |
Output is correct |
41 |
Correct |
3 ms |
4940 KB |
Output is correct |
42 |
Correct |
4 ms |
4940 KB |
Output is correct |
43 |
Correct |
3 ms |
4940 KB |
Output is correct |
44 |
Correct |
3 ms |
5024 KB |
Output is correct |
45 |
Correct |
69 ms |
26196 KB |
Output is correct |
46 |
Correct |
64 ms |
25904 KB |
Output is correct |
47 |
Correct |
69 ms |
26296 KB |
Output is correct |
48 |
Correct |
70 ms |
15760 KB |
Output is correct |
49 |
Correct |
74 ms |
16688 KB |
Output is correct |
50 |
Correct |
76 ms |
16916 KB |
Output is correct |
51 |
Correct |
3 ms |
5024 KB |
Output is correct |
52 |
Correct |
21 ms |
8916 KB |
Output is correct |
53 |
Correct |
73 ms |
16820 KB |
Output is correct |
54 |
Correct |
95 ms |
16924 KB |
Output is correct |
55 |
Correct |
69 ms |
17288 KB |
Output is correct |
56 |
Correct |
80 ms |
17696 KB |
Output is correct |
57 |
Correct |
73 ms |
16048 KB |
Output is correct |
58 |
Correct |
89 ms |
16920 KB |
Output is correct |
59 |
Correct |
25 ms |
8944 KB |
Output is correct |
60 |
Correct |
88 ms |
15620 KB |
Output is correct |
61 |
Correct |
89 ms |
16708 KB |
Output is correct |
62 |
Correct |
91 ms |
16964 KB |
Output is correct |
63 |
Correct |
86 ms |
17000 KB |
Output is correct |
64 |
Correct |
92 ms |
17028 KB |
Output is correct |
65 |
Correct |
75 ms |
16964 KB |
Output is correct |
66 |
Correct |
68 ms |
17096 KB |
Output is correct |
67 |
Correct |
50 ms |
13752 KB |
Output is correct |
68 |
Correct |
50 ms |
13704 KB |
Output is correct |
69 |
Correct |
50 ms |
13720 KB |
Output is correct |
70 |
Correct |
51 ms |
13820 KB |
Output is correct |