[POI2006]MET-Subway

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

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;

}

巴特西