{"problem":{"name":"[XJTUPC 2024] 圣诞树","description":{"content":"有一棵 $n$ 个点的树，点的编号为 $1\\sim n$，每个树的结点都有一个颜色，用 $col_i$ 表示。不同的 $col_i$ 代表不同的颜色。 小 L 要用这棵树制作很多棵圣诞树。一棵树能够被制作成圣诞树，当且仅当它有至少 $k$ ​种不同的颜色。小 L 要把树分成若干互不相交的联通块，并且取出满足条件的联通块制作圣诞树。 在给出这棵树的形态后，问最多能制作出多少棵圣诞树？","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10531"},"statements":[{"statement_type":"Markdown","content":"有一棵 $n$ 个点的树，点的编号为 $1\\sim n$，每个树的结点都有一个颜色，用 $col_i$ 表示。不同的 $col_i$ 代表不同的颜色。\n\n小 L 要用这棵树制作很多棵圣诞树。一棵树能够被制作成圣诞树，当且仅当它有至少 $k$ ​种不同的颜色。小 L 要把树分成若干互不相交的联通块，并且取出满足条件的联通块制作圣诞树。\n\n在给出这棵树的形态后，问最多能制作出多少棵圣诞树？\n\n## Input\n\n输入第一行两个正整数 $n,k$ ($1\\le k \\le n \\le 2\\times 10^5$)，用空格隔开。\n\n第二行 $n$ 个正整数 $col_i$ ($1\\le col_i \\le n$)，代表结点 $i$ 的颜色，两两之间用空格隔开。\n\n接下来 $n-1$ 行，每行两个正整数 $x,y$ ($1\\le x,y \\le n$，$x \\neq y$)，代表树上一条边的两个端点，用空格隔开。\n\n## Output\n\n输出一行一个整数，表示你的答案。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10531","tags":["2024","O2优化","高校校赛"],"sample_group":[["4 2\n1 2 3 4\n1 2\n1 3\n1 4\n","1\n"],["4 2\n1 2 3 4\n1 2\n2 3\n3 4\n","2\n"]],"created_at":"2026-03-03 11:09:25"}}