题目大意
一个有 $ n $ 个节点的树，对于任意一个点 $ v $ 为根的子树如果树上的颜色 $ \ge k $ 那么就把 $ v $ 为根的子树删去答案就加一。
思路
这个地方我们第一个就会想到贪心当一颗子树颜色 $ \ge k $ 时就立马删掉这一颗树答案加一，在操作时用 set 来维护就行了。
在这我介绍一下 set：
set 是 C++ 标准库中的一个容器，属于关联容器的一种。
它是一个有序集合，其中的元素是唯一的，即每个元素只能在集合中出现一次。
set 是基于红黑树实现的合并一次的时间复杂度为 $ \Omicron(n\log n) $ 所以这道题的总时间复杂度为 $ \Omicron(n\log^2 n) $。
当你了解 set 后就可以去写代码了。代码量极少这题代码量和思路与 CF 的一道题好像啊。
注意！
-
如果你直接去写代码会发现 MLE 所以我们需要加一个判断当 $ u $ 的儿子 $ v $ 的颜色大于 $ u $ 那么交换一下他两的颜色统计数组，但是也不能在 $ u $ 添加完 $ v $ 子树的颜色后将 $ v $ 清空因为这样会超时。
-
记得开
long long。 -
记得存双边因为是树。
Code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#define sc(ppt) scanf("%lld" , &ppt)
#define ll long long
#define prt printf
using namespace std;
const ll maxn = 2e5 + 1;
struct edge{
ll next , to;
}e[maxn << 1];
ll n , k , ans = 0 , col[maxn] , h[maxn] , cnt = 0;
set<ll> Size[maxn];
inline void add_edge(ll u , ll v){
++ cnt;
e[cnt].next = h[u] ;
e[cnt].to = v;
h[u] = cnt;
} //链式前向心
void dfs(ll u , ll fa){ // 爬树板子
Size[u].insert(col[u]);
for(ll i=h[u] ; i ; i=e[i].next){
ll v = e[i].to;
if(v == fa) continue;
dfs(v , u);
if(Size[u].size() < Size[v].size()) Size[u].swap(Size[v]); //如果v的颜色大与u颜色的数量那么就swap不然内存会超出限制而且v为子树的颜色数量也没有达到k的要求所以可以换
for(auto j : Size[v]){
Size[u].insert(j);
}
}
ll Sz = Size[u].size();
if(Sz >= k){
Size[u].clear();
++ ans;
}
}
signed main(){
sc(n) ; sc(k) ;
for(ll i=1 ; i<=n ; i++) sc(col[i]);
for(ll i=1 ; i<n ; i++){
ll u , v ; sc(u) ; sc(v) ;
add_edge(u , v);
add_edge(v , u);
}
dfs(1 , -1);
prt("%lld" , ans);
return 0;
}