给定一棵有 n 个结点的树,结点编号为 1 到 n,其中结点 1 是树根。现在 需要在这棵树上选择一些结点进行染色。
树上有 m 个关键结点。对于每个关键结点 x,设其子树大小为 s(子树包 含 x 本身及其所有后代),则以 x 为根的子树中,被染色的结点数必须不少于 ⌈ s 2 ⌉。
请你求出,在满足所有关键结点要求的前提下,最少需要染色多少个结点。
输入共 n + 1 行。 第一行包含两个整数 n, m,分别表示结点总数和关键结点数量;
第二行包含 m 个互不相同的整数,表示所有关键结点的编号;
接下来 n − 1 行,每行包含两个整数 a, b,表示结点 a 和结点 b 之间有一条 边。
输出一个整数,表示最少需要染色的结点总数。
10 5 3 4 5 7 10 1 2 1 3 1 4 3 5 3 6 3 7 5 8 5 9 6 10
5
【样例说明】
一种最优方案是将结点 4, 5, 7, 9, 10 染色,共 5 个结点。
【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ n ≤ 200; 对于所有的评测用例,1 ≤ m ≤ n ≤ 100000,1 ≤ a, b ≤ n。