G. 森林

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给定一个整数 和一棵大小为 的带边权有根树 ,节点编号为 ,根节点编号为 。定义一颗树的大小为其每个叶子节点到其根节点的路径长度之和。求最少可以在 上删除多少个节点,使得形成的森林中每棵树的大小均不超过

注:森林指一个集合,其中每一个元素都是树;显然,删除一棵树的若干节点后,这棵树会分裂成若干棵树,这些树的组合就是一个森林。当删除一个节点后,与该节点所连接的边均消失,因此其所有的下一层节点都变成了森林中的根节点;当一个节点没有任何子节点时,其变为叶子节点。

输入格式

第一行两个整数 ,表示树的大小和给定的整数。

接下来 行,每行两个整数 ,表示 号节点的父节点编号以及连接这两个节点的边权。

题目保证一定会给出一棵树。

输出格式

一行一个整数 ,表示最小需要删除的节点个数。

样例

样例输入一

5 3
1 3
2 2
1 2
2 1

样例输出一

1

样例输入二

1 3

样例输出二

0

样例解释

第一个样例中,删除节点 后,得到有 棵树的森林:,大小分别为:

数据范围与提示

1 \leq n \leq 2\times 10^5,\ 0 \leq S \leq 10^9

1 \leq f \leq n,\ 1 \leq w \leq 10^5