/**
* author: tourist
* created: 17.04.2025 15:40:37
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int get(int x) {
if (p[x] == x) {
return x;
}
return p[x] = get(p[x]);
}
bool unite(int u, int v) {
u = get(u);
v = get(v);
if (u != v) {
p[v] = u;
return true;
}
return false;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> s(n);
vector<vector<int>> at(k);
for (int i = 0; i < n; i++) {
cin >> s[i];
--s[i];
at[s[i]].push_back(i);
}
vector<int> tin(n), tout(n);
vector<vector<int>> pv(n, vector<int>(19));
int timer = 0;
auto Dfs = [&](auto&& self, int v, int pr) -> void {
tin[v] = timer++;
pv[v][0] = pr;
for (int u : g[v]) {
if (u != pr) {
self(self, u, v);
}
}
tout[v] = timer;
};
Dfs(Dfs, 0, -1);
for (int j = 1; j < 19; j++) {
for (int i = 0; i < n; i++) {
if (pv[i][j - 1] == -1) {
pv[i][j] = -1;
} else {
pv[i][j] = pv[pv[i][j - 1]][j - 1];
}
}
}
auto Anc = [&](int u, int v) {
return (tin[u] <= tin[v]) && (tout[v] <= tout[u]);
};
auto lca = [&](int u, int v) {
if (Anc(u, v)) {
return u;
}
for (int b = 18; b >= 0; b--) {
if (pv[u][b] != -1 && !Anc(pv[u][b], v)) {
u = pv[u][b];
}
}
assert(pv[u][0] != -1);
return pv[u][0];
};
vector<int> values(n);
auto Add = [&](int u, int v) {
if (Anc(u, v)) {
values[u] += 1;
values[v] -= 1;
return;
}
if (Anc(v, u)) {
values[v] += 1;
values[u] -= 1;
return;
}
int w = lca(u, v);
values[w] += 1;
values[u] -= 1;
values[v] -= 1;
};
for (int i = 0; i < k; i++) {
sort(at[i].begin(), at[i].end(), [&](int u, int v) {
return (tin[u] < tin[v]);
});
for (int j = 0; j < static_cast<int>(at[i].size()) - 1; j++) {
Add(at[i][j], at[i][j + 1]);
}
}
auto Accumulate = [&](auto&& self, int v, int pr) -> void {
for (int u : g[v]) {
if (u != pr) {
self(self, u, v);
values[v] += values[u];
}
}
};
Accumulate(Accumulate, 0, -1);
dsu ds(n);
for (int v = 1; v < n; v++) {
if (values[v] != 0) {
ds.unite(v, pv[v][0]);
}
}
vector<int> component_values;
for (int v = 0; v < n; v++) {
component_values.push_back(ds.get(v));
}
vector<int> who(n, -1);
int ptr = 0;
for (int i = 0; i < n; i++) {
if (who[component_values[i]] == -1) {
who[component_values[i]] = ptr;
ptr++;
}
}
vector<int> deg(ptr);
for (int v = 1; v < n; v++) {
if (values[v] == 0) {
++deg[who[ds.get(pv[v][0])]];
++deg[who[ds.get(v)]];
}
}
int leaves = 0;
for (int i = 0; i < ptr; i++) {
if (deg[i] == 1) {
leaves++;
}
}
cout << (leaves + 1) / 2 << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |