#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"
using ll = long long;
using ld = long double;
template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}
const int N = 5e5 + 5;
int n, k, timerDFS;
int par[N], h[N], tin[N], lab[N], ids[N], inDeg[N];
vi adj[N], state[N]; map<int, int> mp;
void dfs(int x, int p){
tin[x] = ++timerDFS;
for(int v : adj[x])if(v != p){
par[v] = x, h[v] = h[x] + 1;
dfs(v, x);
}
}
int asc(int x){
return lab[x] < 0 ? x : lab[x] = asc(lab[x]);
}
void join(int u, int v){
u = asc(u), v = asc(v);
if(u != v){
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v], lab[v] = u;
ids[u] = (h[ids[u]] < h[ids[v]] ? ids[u] : ids[v]);
}
}
void pmerge(int u, int v){
while(asc(u) != asc(v)){
if(h[u] < h[v]) swap(u, v);
join(asc(u), par[ids[asc(u)]]);
}
}
void Main()
{
cin >> n >> k;
FOR(i, 1, n - 1){
int u,v; cin >> u >> v;
adj[u].eb(v), adj[v].eb(u);
}
dfs(1, -1);
FOR(i, 1, n){
int x; cin >> x;
state[x].eb(i);
}
FOR(i, 1, n){
ids[i] = i, lab[i] = -1;
}
FOR(cs, 1, k){
sort(all(state[cs]), [&](int x, int y){
return tin[x] < tin[y];
});
FOR(i, 1, sz(state[cs]) - 1){
pmerge(state[cs][i - 1], state[cs][i]);
}
}
auto gid = [&](int x) -> int{
x = asc(x);
if(!mp.count(x)) mp[x] = sz(mp);
return mp[x];
};
FOR(x, 1, n){
for(int v : adj[x]){
if(gid(x) != gid(v)){
++inDeg[gid(v)];
}
}
}
int cnt = 0;
FOR(i, 1, sz(mp)){
if(inDeg[i] == 1){
++cnt;
}
}
cout << (cnt + 1) / 2 << el;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
int t = 1; while(t--) Main();
return 0;
}
Compilation message (stderr)
mergers.cpp: In function 'int32_t main()':
mergers.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | freopen(name".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen(name".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |