#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <stdlib.h>
#include <map>
#include <random>
#include <cstring>
#include <functional>
#include <iomanip>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <array>
using namespace std;
const int inf = 1e9;
const int maxn = 200000;
int par[maxn];
int tin[maxn];
int tout[maxn];
int up[18][maxn];
int upp[18][maxn];
int d[maxn];
vector<int> g[maxn];
vector<int> gp[maxn * 19];
vector<int> rgp[maxn * 19];
int timer = 0;
vector<int> c;
int id = maxn;
void dfs(int v, vector<vector<int>> &g, int p) {
tin[v] = timer++;
up[0][v] = p;
gp[id].push_back(c[v]);
rgp[c[v]].push_back(id);
upp[0][v] = id++;
for (int i = 1; i < 18; ++i) {
up[i][v] = up[i - 1][up[i - 1][v]];
gp[id].push_back(upp[i - 1][up[i - 1][v]]);
gp[id].push_back(upp[i - 1][v]);
rgp[upp[i - 1][v]].push_back(id);
rgp[upp[i - 1][up[i - 1][v]]].push_back(id);
upp[i][v] = id++;
}
for (int u : g[v]) {
if (u != p) {
par[u] = v;
d[u] = d[v] + 1;
dfs(u, g, v);
}
}
tout[v] = timer++;
}
bool isa(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (isa(u, v)) return u;
if (isa(v, u)) return v;
for (int i = 17; i >= 0; --i) {
if (!isa(u, v)) {
u = up[i][u];
}
}
return up[0][u];
}
vector<int> ord;
void dfs(int v, vector<int> *g, vector<bool> &used) {
used[v] = true;
for (int u : g[v]) {
if (!used[u]) {
dfs(u, g, used);
}
}
ord.push_back(v);
}
void dfs(int v, vector<int> *g, vector<int> &color, int cur) {
color[v] = cur;
for (int u : g[v]) {
if (!color[u]) {
dfs(u, g, color, cur);
}
}
}
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
fill(par, par + maxn, -1);
c.resize(n);
for (int& i : c) cin >> i;
for (int& i : c) --i;
dfs(0, g, 0);
for (int i = 0; i < id; ++i) {
gp[i].shrink_to_fit();
rgp[i].shrink_to_fit();
}
vector<vector<int>> groups(k);
for (int i = 0; i < n; ++i) {
groups[c[i]].push_back(i);
}
auto add_edges = [&] (int vertex, int v, int k) {
++k;
for (int i = 17; i >= 0; --i) {
if (k >= (1 << i)) {
gp[vertex].push_back(upp[i][v]);
rgp[upp[i][v]].push_back(vertex);
v = up[i][v];
k -= (1 << i);
}
}
};
for (vector<int> g : groups) {
vector<pair<int, int>> x;
for (int i : g) {
x.push_back({ tin[i], i });
}
sort(x.begin(), x.end());
vector<pair<int, int>> y = x;
for (int i = 0; i + 1 < x.size(); ++i) {
y.push_back({ tin[lca(x[i].second, x[i + 1].second)], lca(x[i].second, x[i + 1].second) });
}
sort(y.begin(), y.end());
vector<int> st;
for (auto [x, v] : y) {
while (!st.empty() && !isa(st.back(), v)) st.pop_back();
if (!st.empty()) {
int k = d[v] - d[st.back()];
add_edges(c[v], v, k);
}
st.push_back(v);
}
}
vector<bool> used(id, false);
for (int i = 0; i < id; ++i) {
if (!used[i]) dfs(i, gp, used);
}
reverse(ord.begin(), ord.end());
vector<int> color(id, 0);
int cur = 1;
for (int i : ord) {
if (!color[i]) {
dfs(i, rgp, color, cur++);
}
}
vector<int> sz(k, 1);
sz.resize(id);
vector<int> sum(id, 0);
for (int i = 0; i < k; ++i) {
sum[color[i] - 1] += sz[i];
}
int res = inf;
--cur;
vector<bool> ok(cur, true);
for (int i = 0; i < id; ++i) {
for (int j : gp[i]) {
if (color[j] != color[i]) {
ok[color[i] - 1] = false;
}
}
}
for (int i = 0; i < cur; ++i) {
if (ok[i] && sum[i]) {
res = min(res, sum[i]);
}
}
cout << res - 1;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
while (t--) {
solve();
}
}
/*
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1 1 2 4 3 3 2 2 3 4 4
6 3
2 1
3 5
6 2
3 4
2 3
1
3 1 2 3 2
*/
Compilation message
capital_city.cpp: In function 'void solve()':
capital_city.cpp:109:16: error: no matching function for call to 'dfs(int, std::vector<int> [200000], int)'
109 | dfs(0, g, 0);
| ^
capital_city.cpp:35:6: note: candidate: 'void dfs(int, std::vector<std::vector<int> >&, int)'
35 | void dfs(int v, vector<vector<int>> &g, int p) {
| ^~~
capital_city.cpp:35:38: note: no known conversion for argument 2 from 'std::vector<int> [200000]' to 'std::vector<std::vector<int> >&'
35 | void dfs(int v, vector<vector<int>> &g, int p) {
| ~~~~~~~~~~~~~~~~~~~~~^
capital_city.cpp:76:6: note: candidate: 'void dfs(int, std::vector<int>*, std::vector<bool>&)'
76 | void dfs(int v, vector<int> *g, vector<bool> &used) {
| ^~~
capital_city.cpp:76:47: note: no known conversion for argument 3 from 'int' to 'std::vector<bool>&'
76 | void dfs(int v, vector<int> *g, vector<bool> &used) {
| ~~~~~~~~~~~~~~^~~~
capital_city.cpp:86:6: note: candidate: 'void dfs(int, std::vector<int>*, std::vector<int>&, int)'
86 | void dfs(int v, vector<int> *g, vector<int> &color, int cur) {
| ^~~
capital_city.cpp:86:6: note: candidate expects 4 arguments, 3 provided
capital_city.cpp:136:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int i = 0; i + 1 < x.size(); ++i) {
| ~~~~~~^~~~~~~~~~
capital_city.cpp:141:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
141 | for (auto [x, v] : y) {
| ^
