SP25476 TAP2015F - Induced favoritism

在一个遥远的王国中，有 $N$ 座城市，编号从 $1$ 到 $N$，其中一些城市通过道路相连。若两座城市直接由一条道路连接，我们称这两座城市为邻居。由于君主的精心规划，王国的道路系统有着独特之处。每对城市之间最多只有一条道路连接，且这些道路总是连接不同的城市。另外，每一对城市之间恰好有唯一的一条路径，这条路径由若干条连接邻近城市的道路组成。

输入包含多组测试数据。每组数据的第一行有两个整数 $N$ 和 $E$，分别表示城市数量和冰壶队的数量（$2 \le N \le 10^5$ 且 $1 \le E \le 100$）。接下来的 $E$ 行描述了各个冰壶队之间的暴动指数。每行包含 $E$ 个整数，第 $i$ 行的第 $j$ 个整数 $D_{ij}$ 表示队伍 $i$ 和队伍 $j$ 间的暴动指数（$0 \le D_{ij} \le 10^9$ 且 $D_{ij} = D_{ji}$）。 接着的 $E$ 行描述了已有城市选择的最喜爱队伍。第 $i$ 行首先包含一个非负整数 $K_i$，接下来的 $K_i$ 个整数代表选择队伍 $i$ 的城市编号（$0 \le K_i \le N$）。每个城市最多有一个最喜爱队伍，且列表中没有重复的城市编号。 最后的 $N-1$ 行描述了城市之间的道路。每行包含两个整数 $A$ 和 $B$，表示城市 $A$ 和城市 $B$ 之间有一条道路（$1 \le A, B \le N$ 且 $A \ne B$）。所有道路是双向的，且没有重复。确保任意两个城市间都有一条唯一的路径，路径可能经过其他城市。

对于每组测试数据，输出一行，表示通过最佳分配各城市的最喜爱队伍所能实现的最小国家暴动指数。

- $2 \le N \le 10^5$ - $1 \le E \le 100$ - $0 \le D_{ij} \le 10^9$ 且 $D_{ij} = D_{ji}$ **本翻译由 AI 自动生成**