#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
if (n == 1) {
std::cout << 0 << "\n";
return 0;
}
std::vector<std::vector<int>> e(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
e[u].push_back(v);
e[v].push_back(u);
}
std::vector<int> c(n);
for (int i = 0; i < n; i++) {
std::cin >> c[i];
c[i]--;
}
std::vector<int> in(n), out(n), L(k, n), R(k);
int timeStamp = 0;
std::function<void(int, int)> dfs = [&](int u, int p) {
in[u] = timeStamp++;
for (auto v : e[u]) {
if (v != p) {
dfs(v, u);
}
}
out[u] = timeStamp;
};
int rt = -1;
for (int i = 0; i < n; i++) {
if (e[i].size() == 1) {
rt = i;
}
}
dfs(rt, rt);
std::vector<bool> vis(k);
std::set<std::pair<int, int>> s;
for (int i = 0; i < n; i++) {
s.emplace(in[i], c[i]);
L[c[i]] = std::min(L[c[i]], in[i]);
R[c[i]] = std::max(R[c[i]], in[i]);
}
std::vector<int> ans(k);
int res = 1e9;
for (int it = 0; it <= k; it++) {
vis.assign(k, false);
for (int i = 0; i < k; i++) {
if (!vis[i]) {
int l = L[i], r = R[i];
bool ok = false;
while (true) {
auto it = s.lower_bound({l, -1});
if (it == s.end() || it->first > r) {
ok = true;
break;
}
if (vis[it->second]) {
s.erase(it);
continue;
}
int color = it->second;
vis[color] = true;
l = std::min(l, L[color]);
r = std::max(r, R[color]);
s.erase(it);
ans[i] += ans[color] + 1;
break;
}
if (ok) {
res = std::min(res, ans[i]);
}
}
}
}
std::cout << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
42904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
