Skip to content

11301: 【原1301】图的染色

题目

题目描述

author: Taring Lee 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1301

Description

给定一棵N个点的无根树,现在你有M次染色机会。每次染色是由你任意选择两个节点u和v,将节点u和v之间的路径上的所有节点染成黑色(包括节点u和v)。

每个点初始颜色是白色,每个点可以被染成黑色任意多次。

现在问最多有多少个节点可以被染成黑色?

Input Format

第一排有两个整数N和M,分别表示点的个数和染色的次数。

以下N-1排,每排有两个整数u,v。表示节点u和节点v之间有一条连边。

Output Format

输出一个整数,为最多被染成黑色的节点的个数。

Sample Input

5 1
1 3
2 3
4 3
5 3

Sample Output

3

Hint

对于10%的数据,1 ≤ M < N ≤ 50;

对于30%的数据,1 ≤ M < N ≤ 3000;

对于100%的数据,1 ≤ M < N ≤ 1000000.

Oops! 本题目还没有解答!

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

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

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