Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
A vertex is only checking for a repeated color across two different child subtrees. If one of the two vertices were itself, then the repeated color would equal , so it would not make cutie.
Do not treat every repeated color as bad. If color repeats below , then is fine when and bad when . So repeated colors create “requests” for the LCA’s color.
Only originally colored vertices can force unavoidable requests. For one fixed color , look at all vertices already colored ; every LCA where two such branches meet requests color .
For each color, you do not need all pairs. Sort its fixed vertices by DFS order; the LCAs of adjacent vertices are enough to recover all LCA nodes of that color’s virtual tree.
After collecting requests: a fixed vertex pays if some requested color differs from its fixed color; an uncolored vertex pays iff at least two different colors request it. Then color uncolored vertices with a requested/subtree color, and fill fully empty parts from the parent.
The definition looks scarier than it is. Let’s de-bullshit it.
For to be cutie, we need two vertices such that and .
If or , then the common color would be , which violates . So both vertices must be strictly below , in two different child subtrees.
So:
is cutie iff some color appears in at least two different child subtrees of .
That is the whole game.
Forced Requests
Look only at vertices whose colors are already fixed. Suppose color appears at two fixed vertices whose LCA is .
Then no matter how we paint the zero vertices, color already appears in two branches under . Therefore:
So every such event is a request: “vertex should be color .”
A fixed vertex cannot change, so one bad request is enough to make it pay. An uncolored vertex can satisfy one requested color, but not two different requested colors. Therefore an uncolored vertex pays exactly when at least two distinct colors request it.
Where Do Requests Come From?
For one color , take the set of fixed vertices with color .
The only useful vertices for this color are:
This is the node set of the virtual tree for color . We do not actually need to build the virtual tree edges. We only need its LCA nodes.
Standard DFS-order fact: if you sort by entry time, then all relevant LCAs appear among adjacent pairs in that order. So for every color:
If is already fixed:
If is uncolored, count color once for that vertex.
Duplicate LCAs for the same color are ignored. One color requesting the same vertex five times is still one request, not five invoices. Even dinosaurs have billing standards.
Minimum Cost
After processing all colors:
This is a lower bound because these requests are created by fixed colored vertices, so we cannot erase them.
Now we need to show the bound is achievable.
Constructing A Coloring
For each uncolored vertex:
Then do a top-down pass. Any still-uncolored vertex has no fixed colored vertex in its subtree, so paint it with its parent’s color. If the root is still uncolored, use color .
Why this does not create extra cost:
So the only vertices that pay are exactly the forced ones counted above.
Complexity
Each fixed colored vertex belongs to exactly one color list. We sort all color lists by DFS order, and the total size over all lists is at most .
The total complexity is:
per test case overall, with memory for binary lifting and extra memory. The sum of is , so this is comfortably fine.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<ll> w(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i];
vector<int> c(n + 1);
vector<vector<int>> byColor(k + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
if (c[i] != 0) byColor[c[i]].push_back(i);
}
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int LOG = 1;
while ((1 << LOG) <= n) LOG++;
vector<vector<int>> up(LOG, vector<int>(n + 1, 1));
vector<int> parent(n + 1, 1), depth(n + 1), tin(n + 1), order;
order.reserve(n);
vector<int> st = {1};
parent[1] = 1;
int timer = 0;
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = timer++;
order.push_back(v);
for (int i = (int)g[v].size() - 1; i >= 0; i--) {
int to = g[v][i];
if (to == parent[v]) continue;
parent[to] = v;
depth[to] = depth[v] + 1;
up[0][to] = v;
for (int j = 1; j < LOG; j++) {
up[j][to] = up[j - 1][up[j - 1][to]];
}
st.push_back(to);
}
}
auto lca = [&](int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) {
if ((diff >> j) & 1) a = up[j][a];
}
if (a == b) return a;
for (int j = LOG - 1; j >= 0; j--) {
if (up[j][a] != up[j][b]) {
a = up[j][a];
b = up[j][b];
}
}
return up[0][a];
};
vector<int> seen(n + 1), reqCnt(n + 1), pick(n + 1);
vector<char> forced(n + 1, false);
for (int col = 1; col <= k; col++) {
auto &vec = byColor[col];
if ((int)vec.size() < 2) continue;
sort(vec.begin(), vec.end(), [&](int a, int b) {
return tin[a] < tin[b];
});
for (int i = 0; i + 1 < (int)vec.size(); i++) {
int v = lca(vec[i], vec[i + 1]);
if (c[v] != 0) {
if (c[v] != col) forced[v] = true;
} else if (seen[v] != col) {
seen[v] = col;
reqCnt[v]++;
pick[v] = col;
}
}
}
vector<int> subColor(n + 1);
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
if (c[v] != 0) subColor[v] = c[v];
for (int to : g[v]) {
if (parent[to] == v && subColor[v] == 0) {
subColor[v] = subColor[to];
}
}
}
ll cost = 0;
vector<int> ans(n + 1);
for (int v = 1; v <= n; v++) {
if (forced[v] || reqCnt[v] > 1) cost += w[v];
if (c[v] != 0) ans[v] = c[v];
else if (reqCnt[v] > 0) ans[v] = pick[v];
else if (subColor[v] != 0) ans[v] = subColor[v];
}
if (ans[1] == 0) ans[1] = 1;
for (int v : order) {
if (v != 1 && ans[v] == 0) ans[v] = ans[parent[v]];
}
cout << cost << '\n';
for (int i = 1; i <= n; i++) {
if (i > 1) cout << ' ';
cout << ans[i];
}
cout << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<ll> w(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i];
vector<int> c(n + 1);
vector<vector<int>> byColor(k + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
if (c[i] != 0) byColor[c[i]].push_back(i);
}
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int LOG = 1;
while ((1 << LOG) <= n) LOG++;
vector<vector<int>> up(LOG, vector<int>(n + 1, 1));
vector<int> parent(n + 1, 1), depth(n + 1), tin(n + 1), order;
order.reserve(n);
vector<int> st = {1};
parent[1] = 1;
int timer = 0;
while (!st.empty()) {
int v = st.back();
st.pop_back();
tin[v] = timer++;
order.push_back(v);
for (int i = (int)g[v].size() - 1; i >= 0; i--) {
int to = g[v][i];
if (to == parent[v]) continue;
parent[to] = v;
depth[to] = depth[v] + 1;
up[0][to] = v;
for (int j = 1; j < LOG; j++) {
up[j][to] = up[j - 1][up[j - 1][to]];
}
st.push_back(to);
}
}
auto lca = [&](int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) {
if ((diff >> j) & 1) a = up[j][a];
}
if (a == b) return a;
for (int j = LOG - 1; j >= 0; j--) {
if (up[j][a] != up[j][b]) {
a = up[j][a];
b = up[j][b];
}
}
return up[0][a];
};
vector<int> seen(n + 1), reqCnt(n + 1), pick(n + 1);
vector<char> forced(n + 1, false);
for (int col = 1; col <= k; col++) {
auto &vec = byColor[col];
if ((int)vec.size() < 2) continue;
sort(vec.begin(), vec.end(), [&](int a, int b) {
return tin[a] < tin[b];
});
for (int i = 0; i + 1 < (int)vec.size(); i++) {
int v = lca(vec[i], vec[i + 1]);
if (c[v] != 0) {
if (c[v] != col) forced[v] = true;
} else if (seen[v] != col) {
seen[v] = col;
reqCnt[v]++;
pick[v] = col;
}
}
}
vector<int> subColor(n + 1);
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
if (c[v] != 0) subColor[v] = c[v];
for (int to : g[v]) {
if (parent[to] == v && subColor[v] == 0) {
subColor[v] = subColor[to];
}
}
}
ll cost = 0;
vector<int> ans(n + 1);
for (int v = 1; v <= n; v++) {
if (forced[v] || reqCnt[v] > 1) cost += w[v];
if (c[v] != 0) ans[v] = c[v];
else if (reqCnt[v] > 0) ans[v] = pick[v];
else if (subColor[v] != 0) ans[v] = subColor[v];
}
if (ans[1] == 0) ans[1] = 1;
for (int v : order) {
if (v != 1 && ans[v] == 0) ans[v] = ans[parent[v]];
}
cout << cost << '\n';
for (int i = 1; i <= n; i++) {
if (i > 1) cout << ' ';
cout << ans[i];
}
cout << '\n';
}
return 0;
}