P17891 [ICPC 2026 Nanchang I] Eating Cherries

题目描述

江桥喜欢吃樱桃!在樱桃还未成熟的时候,他就早早来到了樱桃树前... 一棵樱桃树由 $n$ 个结点(编号 $1$ 到 $n$)和 $n - 1$ 条树枝组成,通过这些树枝把所有结点都连接了起来。 江桥根据每颗樱桃的大小、色泽、甜度等指标把整棵樱桃树上的樱桃分为了 $m$ 种(编号 $1$ 到 $m$),其中第 $i$ 个结点上结了 $k_i$ 种樱桃。 定义一条**主干枝**为樱桃树的根结点到某个边缘结点的不经过重复结点的路径。 即对于根节点 $u$,$u$ 到某个边缘结点 $v$ 的主干枝为一个结点序列 $[u = x_0, x_1, x_2, \ldots, x_s = v]$,其中 $x_i$ 号结点与 $x_{i+1}$ ($i < s$) 号结点通过一条树枝连接,且 $i \neq j$ 时 $x_i \neq x_j$。 **边缘结点**指与其他结点仅有一条树枝连接的结点。特殊地,**根结点不是边缘结点**。 显然对于每个边缘结点,其到根节点的主干枝是唯一确定的。 江桥可以施展魔法。**每次魔法**可以选择一个边缘结点并**任意改变**该结点上樱桃的种类和种类数量(包括将其变为无樱桃)。 他想知道,对于 $1,2,...,n$ 号结点分别作为根节点,**最少需要施展多少次魔法**,才能让每条主干枝上包含的樱桃**种类**均相同。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le 6$),表示树中结点个数和樱桃种类数。 接下来 $n - 1$ 行,每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$),表示树中的一条树枝。 接下来 $n$ 行,第 $i$ 行的第一个整数为非负整数 $k_i$ ($0 \le k_i \le m$),表示 $i$ 号结点所结的樱桃种类数。如果 $k_i > 0$,则后面跟随 $k_i$ 个互不相同的正整数 $t_{i,1}, t_{i,2}, \ldots, t_{i,k_i}$ ($1 \le t_{i,j} \le m$),表示樱桃的种类。 输入数据保证所有结点可以通过树枝相互到达。

输出格式

一行 $n$ 个非负整数,第 $i$ 个数表示 $i$ 号结点为根时的答案。