U140120 漂亮国大选

漂亮国是一个团结、民主的国家。

这个国家有$N$个城市，$N-1$条双向道路连接着这些城市。因为漂亮国是一个团结的国家，所以从任何一个城市你都可以通过道路到达任何其他城市。是的，你是对的——漂亮国的拓扑结构是一棵没有方向的树。 漂亮国有很多党派，每个党派会“把控”一些道路。当然，每条道路只能被一个党派把控。 现在漂亮国要进行总统大选。在大选前，上一任总统有权重新安排所有道路的把控党派。上任总统安排道路的原则是：让整个国家看起来更民主。漂亮国国民对于民主的定义是：如果有一个党派拥有两条或以上的进入某个城市的道路，那么这个城市就不是一个民主的城市。 假设你是漂亮国国家道路安排局局长。总统希望，这样不民主的城市的数量不超过$K$个。请你回答总统：最少需要多少个不同的党派把控道路？

无

无

【**样例解释**】  如图是一种满足总统要求的党派安排情况。其中两个党派分别标为不同的颜色，灰色城市是不民主城市。 【**数据范围**】 对于$20\%$的数据，保证树为一条链，且$1\le N\le 100$。 对于另$20\%$的数据，保证树为一条链，且$1\le N\le 10^5$。 对于另$30\%$的数据，$1\le N\le 1000$。 对于全部数据， 有$1\le N\le 2\times 10^5,0\le K