PID719 / 独立集
题目描述

对于一棵树,独立集是指两两互不相邻的节点构成的集合——NOIP2012初赛

现在我们把独立集的概念拓展一下。

K-独立集的定义是:节点的一个子集,使得任意两个点之间的距离都>K

按照定义,之前所说的独立集就是1-独立集。

给定一个有N个点的树,我们想知道他的最大k-独立集的大小是多少。

输入格式

第一行两个整数 N, k

之后 N-1 行,每行两个整数,表示一条边的两个端点。所有点的标号在[1, n]内。

输出格式

一个整数表示最大k-独立集的大小

样例输入
样例输出
注释

【样例说明】

样例1:选2、3

样例2:无论如何都不能选一个点以上。

【数据规模和约定】

提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论