4. 工业帝国
XJOI - 题目ID：15610必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述
阿斯罗菲克帝国是大陆三大帝国中最北方的一个。费尔巴哈大帝认为工业发展程度才是一个帝国实力最重要的体现，因此他决定在帝国的 n 座城市里选定恰好 k 座城市建立工业基地。帝国的 n 座城市由 n-1 条双向通行的道路连接，且从任意一个城市都可以到达其它任意一座城市，大帝所在的 1 号城市就是帝国的首都。
每一年，大帝都会召开帝国工业大会，并下令每一个工业基地都派一位代表来首都参会，每一位代表都会走最短路径到达首都。但是由于代表待在工业基地的时间太久了，他们出来开会时总是想经过尽可能多的没有工业基地的城市。大帝体恤民情，因此希望选取 k 座城市建立工业基地后，每次开会的代表都能够经过尽可能多的没有工业基地的城市。
请问每年代表经过的没有工业基地的城市数量总和最多是多少。
输入格式
第一行两个整数 n 和 k，接下来 n-1 行每行两个整数表示一条双向通行的路径。
输出格式
输出一行一个整数表示答案。
样例输入
7 4
1 2
1 3
1 4
3 5
3 6
4 7
样例输出
7
样例输入
4 1
1 2
1 3
2 4
样例输出
2
样例输入
8 5
7 5
1 7
6 1
3 7
8 3
2 1
4 5
样例输出
9
数据规模
2≤�≤2⋅1052≤n≤2⋅105，1≤�<�1≤k<n
思路是对的，但样例过不了