http://codeforces.com/problemset/problem/414/D

Mashmokh is playing a new game. In the beginning he has k liters of water and p coins. Additionally he has a rooted tree (an undirected connected acyclic graph) that consists of m vertices. Each vertex of the tree contains a water tank that is empty in the beginning.

The game begins with the fact that Mashmokh chooses some (no more than k) of these tanks (except the root) and pours into each of them exactly 1 liter of water. Then the following process is performed until there is no water remained in tanks.

  • The process consists of several steps.
  • At the beginning of each step Mashmokh opens doors of all tanks. Then Mashmokh closes doors of some tanks (he is not allowed to close door of tank in the root) for the duration of this move. Let's denote the number of liters in some tank with closed door as w, Mashmokh pays w coins for the closing of that tank during this move.
  • Let's denote by x1, x2, ..., xm as the list of vertices of the tree sorted (nondecreasing) by their depth. The vertices from this list should be considered one by one in the order. Firstly vertex x1 (which is the root itself) is emptied. Then for each vertex xi (i > 1), if its door is closed then skip the vertex else move all the water from the tank of vertex xi to the tank of its father (even if the tank of the father is closed).

Suppose l moves were made until the tree became empty. Let's denote the amount of water inside the tank of the root after the i-th move by wi then Mashmokh will win max(w1, w2, ..., wl) dollars. Mashmokh wanted to know what is the maximum amount of dollars he can win by playing the above game. He asked you to find this value for him.

Input

The first line of the input contains three space-separated integers m, k, p (2 ≤ m ≤ 105; 0 ≤ k, p ≤ 109).

Each of the following m - 1 lines contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ m; ai ≠ bi) — the edges of the tree.

Consider that the vertices of the tree are numbered from 1 to m. The root of the tree has number 1.

Output

Output a single integer, the number Mashmokh asked you to find.

 

题意：

给你一棵树，k升水，p块钱，进行一次游戏。

　　在游戏进行前，可以在任意个节点上放置1升水（总数不超过k）

　　游戏进行若干轮，每轮游戏开放所有节点，可以选择若干个节点关闭，代价为该节点的水数量。然后所有未关闭的节点的水流向它的父亲(不会连续移动)。最后，根节点中的水会被取走，水的数量为该轮游戏的盈利。

　　求盈利最大的某轮游戏的盈利。

思路：

贪心策略：尽量放深度连续的一段。这是为什么呢？画个图理解一下：

1.首先明白一点，假设选的点集为V，包含了深度[l,r]，那么任意深度为i的点x对答案贡献是r-i。从下往上依次阻遏和一直在l处阻遏的花费是一样的。

2.如上图，把选2换成选6，选点数不变，而花费减少，更优。（总层数减少）

3.把选4，5，7，8，9任一点换成选13，选点数不变，而花费减少，更优。（总层数不变）

因此，最优的策略是：先选定某一行r，全选中，然后往上尽量多选点，非l一定要选满。

PS：自己一开始错误的贪心方法是：二分x，即确定选x个点，判断能否在p块钱内满足，我错误地认为一定是从根结点的子结点逐层往下尽量选满一层，但实际上未必是最上面几层。中间的[l,r]全汇集到l之后也就相当于是完成了。

关于具体做法，先将深度排序。然后维护双指针l和r，每次移动r，然后选尽量范围大且合法的l，扫一遍就行了。

是一个线性时间的做法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100000+100

int n,k,p,ans;
vector<int> G[maxn],depth;

void dfs(int u,int fa,int d)
{
	depth.push_back(d);
	for(int j=0;j<G[u].size();j++)
	{
		int v=G[u][j];
		if(v==fa)continue;
		dfs(v,u,d+1);
	}
}

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>k>>p;
	int x,y;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0,0);
	sort(depth.begin(),depth.end());
	int l=1,r=0,cost=0;
	while(r+1<depth.size())
	{
		r++;
		if(depth[r]!=depth[r-1])cost+=r-l;
		while(cost>p||r-l+1>k)
		{
			cost-=depth[r]-depth[l];
			l++;
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans<<endl;
	return 0;
}