陶陶吃苹果

陶陶吃苹果

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

陶陶很喜欢吃苹果。

描述

curimit知道陶陶很喜欢吃苹果。于是curimit准备在陶陶生日的时候送给他一棵苹果树。

curimit准备了一棵这样的苹果树作为生日礼物:这棵苹果树有n个节点,每个节点上有c[i]个苹果,这棵树高度为h。

可是,当curimit把这棵树给陶陶看的时候,陶陶却说:“今年生日不收礼,收礼只收节点数减高度不超过k的苹果树。”这下curimit犯难了,curimit送来的树枝繁叶茂,不满足节点数-高度≤k。于是curimit决定剪掉一些枝条,使得修剪过后的树满足节点数-高度≤k,但是curimit又想保留尽量多的苹果数目。curimit想请你帮他算算经过修剪后的树最多能保留多少个苹果。

注:
一, 节点1为树根,不能把它剪掉。

二, 1个节点的树高度为1。

格式

输入格式

输入文件的第一行为两个整数n,k分别表示这棵树有n个节点,修剪后的树节点数-高度≤k。

第二行开始到第n+1行,每行有两个数,第i+1行的两个数father[i]和c[i]分别表示节点i的父亲是father[i]和节点i处有c[i]个苹果。

规定:节点1的父亲为0。

输出格式

输出文件仅包含一行,ans,表示在满足修建后的树节点数-高度≤k的条件下,最多能保留多少个苹果。

样例1

样例输入1

5 1
0 1
1 1
1 3
2 10
3 4

样例输出1

15

限制

全部1秒

提示

【约定】
对于10%的数据, n≤10
对于30%的数据, n≤100 0≤k≤20
对于100%的数据,n≤4000 0≤k≤=500

来源

原创题。

第一届Curimit模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2009-10-25 18:30
结束于
2009-10-25 22:17
持续时间
3.8 小时
主持人
参赛人数
1382