OI题库

引爆炸弹

问题描述：

有n个炸弹，有些炸弹牵了一根单向引线（也就是说引线只有在这一端能被炸弹点燃），只要引爆了这个炸弹，用引线连接的下一个炸弹也会爆炸。每个炸弹还有个得分，当这个炸弹被引爆后就能得到相应得分。

现在要你引爆k个炸弹，使得分最大。

 

输入说明：

第1行两个整数n、k。

接下来n行每行两个整数a[i]、b[i]。a[i]表示这个炸弹用引线连接的下一个炸弹，如果a[i]为0，则表示这个炸弹没连接引线。b[i]表示这个炸弹的得分。

 

输出说明：

仅一个数，表示最大得分。

 

样例输入输出：

bombb.in

8 2 0 1 1 1 2 100 2 100 0 1 5 1 6 2 6 2

bombb.out

202

 

数据范围：

    1≤b[i]≤1000000

    对于30%的数据，n≤1000  k≤30

对于60%的数据，n≤50000 k≤100

对于100%的数据，n≤200000   k≤500