题目 3396:

蓝桥杯2026年第十七届省赛真题-子树染色

 时间限制: 1s 内存限制: 128MB

题目描述

给定一棵有 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。

标签