Description
给出一棵N个结点的树，选择L条路径，覆盖这些路径上的结点，使得被覆盖到的结点数最多。
Input
第一行两个正整数N、L(2 <= N <= 1,000,000, 0 <= L <= N)。下面有N-1行，每行两个正整数A和B(1 <= A, B <= N)，表示一条边(A,B)。
Output
一个整数，表示最多能覆盖到多少结点。
Sample Input
17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10
Sample Output
13
Solution
这个题么，还是很容易想的吧。首先，我们随便画出一棵树来，然后YY一下，发现对于所有的叶子节点，我们最多选到\(min(2\times l ,sum_{leaves})\)个节点。那么，思考一下我们是不是可以把这个结论推广到这棵树的每一层上，事实证明，完全没有问题。那么，如何给这棵树分层呢？比较好的方法是从这棵树的所有叶子节点来一遍拓扑排序，记录一下就可以了。
Code
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define MAXN 1000001
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
struct po
{
int nxt,to;
}edge[MAXN*2];
int head[MAXN],du[MAXN],cur[MAXN],n,m,stack[MAXN],vis[MAXN],l,cnt[MAXN],ans,num;
inline void add_edge(int from,int to)
{
edge[++num].nxt=head[from];
edge[num].to=to;
head[from]=num;
}
inline void add(int from,int to)
{
add_edge(from,to);
add_edge(to,from);
}
inline int read()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-') c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
queue<int> q;
inline void top()
{
for(re int i=1;i<=n;i++) if(du[i]==1) ++cnt[cur[i]=1],vis[i]=1,q.push(i);
while(!q.empty()){
int u=q.front();
q.pop();
for(re int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(vis[v]) continue;
du[v]--;
if(du[v]==1) {
vis[v]=1;
++cnt[cur[v]=cur[u]+1];
q.push(v);
}
}
}
return;
}
int main()
{
n=read();l=read();
for(re int i=1;i<n;i++){
int x=read(),y=read();
du[x]++;du[y]++;
add(x,y);
}
top();
for(re int i=1;cnt[i];i++){
ans+=min(l<<1,cnt[i]);
}
cout<<ans;
return 0;
}