#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5, nbit = 19;
int n, k;
vector<int> g[nmax];
int pin[nmax], pout[nmax], inp = 1;
namespace LCA {
int p[nmax][nbit];
void init(int node, int f) {
pin[node] = inp++;
p[node][0] = f;
for(int i = 1; i < nbit; i++)
p[node][i] = p[p[node][i - 1]][i - 1];
for(auto x : g[node])
if(x == f) continue;
else init(x, node);
pout[node] = inp++;
}
bool isanc(int x, int y) {return pin[x] <= pin[y] && pout[y] <= pout[x]; }
int lca(int x, int y) {
if(isanc(x, y)) return x;
if(isanc(y, x)) return y;
for(int i = nbit - 1; i >= 0; i--)
if(!isanc(p[x][i], y))
x = p[x][i];
return p[x][0];
}
};
vector<int> ofcol[nmax];
int lca[nmax];
int start[nmax], fin[nmax];
int cnt;
vector<int> cuts;
int identify(int node, int f) {
int sum = start[node] + fin[node];
for(auto x : g[node]) {
if(x == f) continue;
int tmp = identify(x, node);
if(tmp == 0)
cuts.push_back(x);
else
sum += tmp;
}
return sum;
}
int noise_reduction(int node, int f) {
int sum = 0;
for(auto x : g[node]) {
if(x == f) continue;
sum += noise_reduction(x, node);
}
if((sum == 0 && start[node] == 1))
cnt++;
return !start[node] * sum + start[node];
}
signed main() {
cin >> n >> k;
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
LCA::init(1, 1);
AIB::init(inp);
for(int i = 1, x; i <= n; i++) {
cin >> x;
ofcol[x].push_back(i);
}
for(int i = 1; i <= k; i++) {
lca[i] = ofcol[i].back();
for(auto x : ofcol[i])
lca[i] = LCA::lca(x, lca[i]);
for(auto x : ofcol[i])
start[x]++,
fin[lca[i]]--;
}
identify(1, 1);
cuts.push_back(1);
for(int i = 1; i <= n; i++)
start[i] = 0;
for(auto x : cuts)
start[x] = 1;
noise_reduction(1, 1);
cout << (cnt + 1) / 2 << '\n';
}
/**
De-atâtea nopți aud plouând,
Aud materia plângând..
Sînt singur, și mă duce un gând
Spre locuințele lacustre.
Și parcă dorm pe scânduri ude,
În spate mă izbește-un val --
Tresar prin somn și mi se pare
Că n-am tras podul de la mal.
Un gol istoric se întinde,
Pe-același vremuri mă găsesc..
Și simt cum de atâta ploaie
Pilonii grei se prăbușesc.
De-atâtea nopți aud plouând,
Tot tresărind, tot așteptând..
Sînt singur, și mă duce-un gând
Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:79:3: error: 'AIB' has not been declared
79 | AIB::init(inp);
| ^~~
