#include "bits/stdc++.h"
using namespace std;
//#include "debug.h"
const int N = (int) 5e5 + 22;
const int inf = (int) 1e9;
vector<array<int, 3>> states;
int K;
struct Data {
int dp[2][2][3]; // bad(tomin), good(tomin), empty(0)
void init(int x) {
for (auto [i, j, k] : states) {
dp[i][j][k] = inf;
}
if (x == 0 || x == -1) {
dp[0][0][2] = 0;
}
if (x == 1 || x == -1) {
dp[1][0][2] = 0;
}
}
void upd(int i, int j, int k, int val) {
if (k == 2) {
val = 0;
}
if (k == 0 && val >= K) {
//
} else {
dp[i][j][k] = min(dp[i][j][k], val);
}
}
};
int n, a[N];
Data dp[N];
vector<int> g[N];
Data merge(const Data& a, const Data& b) {
Data res;
res.init(-2);
// debug(b.dp[1][1][0]);
for (auto [i, j, k] : states) {
if (a.dp[i][j][k] == inf) {
continue;
}
for (auto [i2, j2, k2] : states) {
if (b.dp[i2][j2][k2] == inf) {
continue;
}
int adp = a.dp[i][j][k];
int bdp = b.dp[i2][j2][k2];
// if (i2 == 1 && j2 == 1 && k2 == 0) {
// debug(bdp);
// }
bdp++;
if (i == i2) {
// dp[i][1]
if (k == 2 && k2 == 2) {
res.upd(i, 1, 2, 0);
} else if (k == 2) {
res.upd(i, 1, k2, bdp);
} else if (k2 == 2) {
res.upd(i, 1, k, adp);
} else {
if (adp + bdp <= K) {
k = k2 = 1;
}
if (k && k2) {
res.upd(i, 1, 1, min(adp, bdp));
} else {
res.upd(i, 1, 0, k ? bdp : k2 ? adp : max(adp, bdp));
}
}
} else {
// if (i == 0 && j == 1 && k == 2 && i2 == 1 && j2 == 1 && k2 == 0) {
// debug(adp, bdp);
// }
if (k2 != 2 && bdp <= K) {
j = 1;
k2 = 1;
}
if (k != 2 && adp + 1 <= K) {
j2 = 1;
k = 1;
}
if (!k2 || (!j2 && 1 >= K) || (!k && adp >= K)) {
continue;
}
// res[i][j][...]
if (k == 2) {
res.upd(i, j, j2, 1);
} else if (k == 1) {
res.upd(i, j, j2, 1);
} else {
res.upd(i, j, k, adp);
}
}
}
}
return res;
}
void dfs(int v, int pr) {
dp[v].init(a[v]);
for (auto u : g[v]) {
if (u != pr) {
dfs(u, v);
// if (v == 1 && u == 3) {
// debug(dp[v].dp[0][1][2]);
// debug(dp[u].dp[1][1][0]);
// }
dp[v] = merge(dp[v], dp[u]);
// debug(v);
}
}
}
bool check(int _) {
K = _;
// debug(K);
dfs(0, 0);
// if (K == 6) {
// debug(dp[0].dp[1][1][1]);
// debug(dp[3].dp[1][1][0]);
// debug(dp[1].dp[0][1][1]);
// debug(dp[2].dp[0][0][2]);
// }
for (int it = 0; it < 2; it++) {
if (dp[0].dp[it][1][1] != inf) {
return true;
}
if (dp[0].dp[it][1][2] != inf) {
return true;
}
}
return false;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
g[i].clear();
}
for (int i = 0, x, y; i + 1 < n; i++) {
cin >> x >> y;
x--, y--;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int l = 0, r = n;
if (!check(r)) {
cout << -1 << '\n';
} else {
while (l + 1 < r) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
cout << r << '\n';
for (int i = 0; i < n; i++) {
cout << max(0, a[i]) << " ";
}
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
states.push_back({i, j, k});
}
}
}
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14928 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
14928 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
15176 KB |
Output is correct |
| 2 |
Correct |
190 ms |
18764 KB |
Output is correct |
| 3 |
Correct |
157 ms |
15388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
15176 KB |
Output is partially correct |
| 2 |
Correct |
230 ms |
35504 KB |
Output is partially correct |
| 3 |
Correct |
135 ms |
24096 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
18000 KB |
Output is partially correct |
| 2 |
Correct |
108 ms |
15088 KB |
Output is partially correct |
| 3 |
Correct |
126 ms |
15136 KB |
Output is partially correct |
| 4 |
Correct |
74 ms |
15176 KB |
Output is partially correct |
| 5 |
Correct |
93 ms |
15180 KB |
Output is partially correct |
| 6 |
Correct |
153 ms |
15220 KB |
Output is partially correct |
| 7 |
Correct |
111 ms |
15184 KB |
Output is partially correct |
| 8 |
Correct |
74 ms |
15104 KB |
Output is partially correct |
| 9 |
Correct |
93 ms |
15176 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14928 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
14928 KB |
Output isn't correct |
| 3 |
Correct |
92 ms |
15176 KB |
Output is correct |
| 4 |
Correct |
190 ms |
18764 KB |
Output is correct |
| 5 |
Correct |
157 ms |
15388 KB |
Output is correct |
| 6 |
Correct |
93 ms |
15176 KB |
Output is partially correct |
| 7 |
Correct |
230 ms |
35504 KB |
Output is partially correct |
| 8 |
Correct |
135 ms |
24096 KB |
Output is partially correct |
| 9 |
Correct |
179 ms |
18000 KB |
Output is partially correct |
| 10 |
Correct |
108 ms |
15088 KB |
Output is partially correct |
| 11 |
Correct |
126 ms |
15136 KB |
Output is partially correct |
| 12 |
Correct |
74 ms |
15176 KB |
Output is partially correct |
| 13 |
Correct |
93 ms |
15180 KB |
Output is partially correct |
| 14 |
Correct |
153 ms |
15220 KB |
Output is partially correct |
| 15 |
Correct |
111 ms |
15184 KB |
Output is partially correct |
| 16 |
Correct |
74 ms |
15104 KB |
Output is partially correct |
| 17 |
Correct |
93 ms |
15176 KB |
Output is partially correct |
| 18 |
Correct |
881 ms |
16400 KB |
Output is partially correct |
| 19 |
Correct |
1050 ms |
23624 KB |
Output is partially correct |
| 20 |
Incorrect |
361 ms |
15944 KB |
Output isn't correct |
| 21 |
Correct |
2911 ms |
54612 KB |
Output is partially correct |
| 22 |
Correct |
1249 ms |
58852 KB |
Output is partially correct |
