Skip to content

1209: 好树

题目

题目描述

给定一颗包含 $N$ 个点的树,树上结点标号 $1$ 到 $N$ 。给定 $K$ 个划分集合,划分集合中元素是树上的结点,且每个划分集合都不是空集,树上每个结点都只会属于其中的某一个划分集合。

现在给定一系列关于这棵树“好坏”的指标。这棵树是“坏”的当且仅当将这棵树的结点分为两组(X组和Y组),且满足以下条件:

  • 所有结点属于X组或Y组之一
  • X组中至少有一个结点
  • Y组中至少有一个结点
  • 对于任意一个划分集合,其中包含的结点均属于同一个组
  • X组中任意一个结点均可通过走树上的边到达X组中的任意其他结点且途中不经过Y组中的结点
  • Y组中任意一个结点均可通过走树上的边到达Y组中的任意其他结点且途中不经过X组中的结点

你现在有合并划分集合的选项:每一次合并需选出两个划分集合并将其合并。现在你需要回答,至少经过多少次合并,才能使得这棵树是“好”的。

输入格式

第一行输入两个正整数 $N$ 和 $K$ ,表示这棵树的结点数和划分集合的个数

接下来 $N-1$ 行,每行两个整数 $u_i, v_i$ ,描述树上的一条边

接下来 $N$ 行,每行一个整数 $S_i$ ,表示树上的 $i$ 号结点属于第 $S_i$ 个划分集合

输出格式

输出一行一个整数表示需要合并的次数

样例输入

样例输入 1

text 5 4 1 2 2 3 3 4 3 5 1 2 1 3 4

样例输入 2

text 5 4 1 2 2 3 3 4 4 5 1 2 3 4 1

样例输出

样例输出 1

text 1

样例输出 2

text 0

数据范围

对于10%的数据, $1\leq N\leq 100$, $1\leq K\leq 7$

另有24%的数据, $1\leq N\leq 3000$

另有14%的数据, $1\leq N\leq 10^5$, $1\leq K\leq 50$

另有22%的数据, $1\leq N\leq 10^5$, 同一个划分集合中的两个结点之间在树上最多只有100条边

对于100%的数据, $1\leq N\leq 5 \times 10^5$, $1\leq K\leq N$, $1\leq u_i, v_i\leq N$, $1\leq S_i\leq K$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!