题目描述
对于一棵树,独立集是指两两互不相邻的节点构成的集合——NOIP2012初赛
现在我们把独立集的概念拓展一下。
K-独立集的定义是:节点的一个子集,使得任意两个点之间的距离都>K
按照定义,之前所说的独立集就是1-独立集。
给定一个有N个点的树,我们想知道他的最大k-独立集的大小是多少。
输入格式
第一行两个整数 N, k
之后 N-1 行,每行两个整数,表示一条边的两个端点。所有点的标号在[1, n]内。
输出格式
一个整数表示最大k-独立集的大小
样例输入
样例输出
注释
【样例说明】
样例1:选2、3
样例2:无论如何都不能选一个点以上。
【数据规模和约定】