3505: Tree Cutting
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $4$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Given a tree (connected undirected graph with n![]()
vertexes and n−1![]()
edges), you are required to delete as few vertexes as possible such that the remaining graph is still a tree and its diameter shall not exceed k![]()
. The diameter of a tree is the length of its longest path.
Input
The first line contains one positive integer T![]()
(1≤T≤15![]()
), denoting the number of test cases. For each test case:
The first line of the input contains two integers n,k(1≤n,k≤300000)![]()
.
Each of the following n−1![]()
lines contains two integers u,v(1≤u,v≤n,u≠v)![]()
, indicating that there is an edge connecting vertex u![]()
and v![]()
in the tree.
The first line of the input contains two integers n,k(1≤n,k≤300000)
Each of the following n−1
Output
For each test case:
You should just output one integer indicating the number of vertexes to be deleted.
You should just output one integer indicating the number of vertexes to be deleted.
Sample Input复制
1
10 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
Sample Output复制
4
推荐代码 查看3505 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 | 梦尘 | 691259 | 2020-12-27 23:26:15 |
赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|