#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MAXN = 100000;
int dp[MAXN+5][2][2];
int dpp[MAXN+5][2][2];
int ndpp[2][2];
int col[MAXN+5];
vector <int> graf[MAXN+5];
void dfs(int v, int p){
bool leaf = 1;
for(int j=0; j<2; j++) for(int k=0; k<2; k++) dpp[v][j][k] = MAXN;
dpp[v][0][0] = 0;
dpp[v][1][0] = 0;
for(auto c : graf[v]){
if(c != p){
dfs(c, v);
leaf = 0;
for(int j=0; j<2; j++) for(int k=0; k<2; k++) ndpp[j][k] = MAXN;
for(int j=0; j<2; j++){
for(int k=0; k<2; k++){
ndpp[j][k] = min(ndpp[j][k], dpp[v][j][k] + dp[c][j][0]);
ndpp[j][k] = min(ndpp[j][k], dpp[v][j][1^k] + dp[c][j][1]);
}
}
for(int j=0; j<2; j++) for(int k=0; k<2; k++) dpp[v][j][k] = ndpp[j][k];
}
}
if(leaf){
dp[v][col[v]][1] = MAXN;
dp[v][1^col[v]][0] = MAXN;
dp[v][1^col[v]][1] = 1;
return;
}
dp[v][col[v]][0] = dpp[v][1][0];
dp[v][1^col[v]][0] = dpp[v][1][1];
dp[v][1^col[v]][1] = 1 + dpp[v][0][0];
dp[v][col[v]][1] = 1 + dpp[v][0][1];
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n;
cin >> n;
for(int i=1; i<n; i++){
int a, b;
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
for(int i=1; i<=n; i++){
cin >> col[i];
col[i] ^= 1;
}
dfs(1, 0);
int res = min(dp[1][1][0], dp[1][1][1]);
if(res >= MAXN) cout << "Impossible\n";
else cout << res << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
19872 KB |
Output is correct |
2 |
Incorrect |
62 ms |
19656 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
19952 KB |
Output is correct |
2 |
Incorrect |
64 ms |
19728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |