Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

瞬(teleport)

你要遍历一棵以 $1$ 为根的 $n$ 个节点的外向树,你走过一条边需要一定的时间。另外,你可以在节点放置分身,你可以瞬移到任何一个分身处;同时,你可以在任何时候收走一个点上的分身。整个树最多同时存在 $k$ 个分身。求最小时间。

输入格式

第一行两个整数 $n,p$ 表示树的大小及最多同时存在的分身数的范围。

接下来 $n-1$ 行中,第 $i$ 行两个整数 $f$ 和 $t$ 表示 $i$ 的 父亲节点编号以及走过 $i$ 的父亲到 $i$ 这条边所需时间。

输出格式

$p$ 行,第 $i$ 行一个整数表示当 $k=i$ 时的最小时间。

数据范围

Subtask1(10%) $n\le 10$

Subtask2(20%) $n\le 20$

Subtask3(30%) $n\le 100$

Subtask4(20%) $p\le 20$

Subtask5(20%) $n\le 1000$

对于所有数据,满足 $1\le p\le n\le 1000,1\le t\le 10^9$,且每个点父亲节点编号小于该点编号。

样例