#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 500005;
int n, m, clr[MXN];
vector<int> sclr[MXN];
struct BIT {
int n, val[MXN];
void init(int _n) {
n = _n;
fill(val + 1, val + n + 1, 0);
}
void modify(int id, int v) {
for (; id <= n; id += (id & -id)) val[id] += v;
}
void modify(int l, int r, int v) {
modify(l, v);
modify(r, -v);
}
int query(int id) {
int ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
} B;
struct DSU {
int p[MXN];
void init(int n) {
fill(p + 1, p + n + 1, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool onion(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y];
p[y] = x;
return true;
}
} dsu;
namespace TREE {
vector<int> edge[MXN];
int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C;
int idfn[MXN];
int deg[MXN];
void PUSH_EDGE(int x, int y) {
edge[x].push_back(y);
edge[y].push_back(x);
}
void DFS(int id, int par, int dep) {
p[id] = par;
d[id] = dep;
sz[id] = 1;
son[id] = -1;
for (auto &i : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
sz[id] += sz[i];
if (son[id] == -1) son[id] = i;
else if (sz[son[id]] < sz[i]) son[id] = i;
}
}
void HLD(int id, int par, int _t) {
top[id] = _t;
dfn[id] = C++;
if (son[id] != -1) HLD(son[id], id, _t);
for (auto &i : edge[id]) {
if (i == par) continue;
if (i == son[id]) continue;
HLD(i, id, i);
}
}
void BUILD() {
DFS(1, 0, 0);
C = 1;
HLD(1, 0, 1);
FOR(i, 1, n) idfn[dfn[i]] = i;
B.init(n);
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
B.modify(dfn[top[x]], dfn[x] + 1, 1);
x = p[top[x]];
}
if (d[x] < d[y]) swap(x, y);
B.modify(dfn[y] + 1, dfn[x] + 1, 1);
return y;
}
void COLOR(vector<int> &v) {
int lca = v[0];
FOR(i, 1, v.size()) {
lca = LCA(lca, v[i]);
}
}
void MERGE() {
vector<int> v;
dsu.init(n);
FOR(i, 2, n + 1) {
if (B.query(dfn[i])) {
debug(i, p[i], 1);
dsu.onion(i, p[i]);
} else {
v.push_back(i);
}
}
for (auto &i : v) {
debug(i, p[i], 0);
deg[dsu.find(i)]++;
deg[dsu.find(p[i])]++;
}
}
int LEAF() {
int ans = 0;
FOR(i, 1, n + 1) {
if (dsu.p[i] >= 0) continue;
if (deg[i] <= 1) ans++;
}
return ans;
}
}
int miku() {
int x, y;
cin >> n >> m;
FOR(i, 1, n) {
cin >> x >> y;
TREE::PUSH_EDGE(x, y);
}
TREE::BUILD();
FOR(i, 1, n + 1) {
cin >> clr[i];
sclr[clr[i]].push_back(i);
}
FOR(i, 1, m + 1) TREE::COLOR(sclr[i]);
TREE::MERGE();
// cout << (TREE::LEAF() - 1) / 2 + 1 << '\n';
int x = TREE::LEAF();
if (x == 1) return 0;
return (x - 1) / 2 + 1;
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
cout << miku() << '\n';
return 0;
}
Compilation message
mergers.cpp: In function 'void TREE::MERGE()':
mergers.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
mergers.cpp:131:17: note: in expansion of macro 'debug'
131 | debug(i, p[i], 1);
| ^~~~~
mergers.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
mergers.cpp:138:13: note: in expansion of macro 'debug'
138 | debug(i, p[i], 0);
| ^~~~~
mergers.cpp: In function 'long long int miku()':
mergers.cpp:169:9: error: redeclaration of 'long long int x'
169 | int x = TREE::LEAF();
| ^
mergers.cpp:155:9: note: 'long long int x' previously declared here
155 | int x, y;
| ^
