#2645. Vijos1676 陶陶吃苹果
Vijos1676 陶陶吃苹果
题目描述
curimit 知道陶陶很喜欢吃苹果。于是 curimit 准备在陶陶生日的时候送给他一棵苹果树。
curimit 准备了一棵这样的苹果树作为生日礼物:这棵苹果树有 个节点,每个节点上有 个苹果,这棵树高度为 。
可是,当 curimit 把这棵树给陶陶看的时候,陶陶却说:“今年生日不收礼,收礼只收节点数减高度不超过 的苹果树。”这下 curimit 犯难了,curimit 送来的树枝繁叶茂,不满足节点数-高度 。于是 curimit 决定剪掉一些枝条,使得修剪过后的树满足节点数减高度 ,但是 curimit 又想保留尽量多的苹果数目。curimit 想请你帮他算算经过修剪后的树最多能保留多少个苹果。
注:
- 节点 1 为树根,不能把它剪掉。
- 1 个节点的树高度为 1。
输入格式
输入文件的第一行为两个整数 分别表示这棵树有 个节点,修剪后的树节点数减高度 。
第二行开始到第 行,每行有两个数,第 行的两个数 和 分别表示节点 的父亲是 和节点 处有 个苹果。
规定:节点 1 的父亲为 0。
输出格式
输出文件仅包含一行,表示在满足修建后的树节点数减高度 的条件下,最多能保留多少个苹果。
10 3
0 89928
1 38219
1 91615
2 5517
3 15244
3 78458
1 76512
4 99582
7 64607
1 91175
494494
数据规模与约定
对于 的数据,。
对于 的数据,,。
对于 的数据,,。
题目来源
Vijos1676