2. 摘 Galo(OvO) 1s/512M

[XOJ]仅评测链接

2.1 题目描述:

0v0 在野外看到了一棵 Galo 树,看到食物的 0v0 瞪大了眼睛,变成了 OvO 。

这棵 Galo 树可以看做是一棵以 1 号点为根的n个点的有根树,除了根节点
以外,每个节点i都有一个 Galo ,美味度为w[i]
OvO 发现,如果她摘下了i号 Galo ,那么i的子树中的 Galo 以及i到根的
路径上的其他 Galo 都会死掉。
OvO 的袋子只能装k个 Galo ,她的嘴巴里还能叼 1 个,请问她所摘 Galo
的美味度之和的最大值是多少?

2.2 输入格式:

第一行两个正整数n,k
第二行到第n行,第i行两个正整数 f[i]w[i],表示i号点的父亲为f[i](保
f[i]<i),第iGalo 美味度为w[i]

2.3 输出格式
一行一个非负整数,为最大美味值。
2.4 样例输入
4 1
1 10
2 3
2 6
2. 5 样例输出
10
2. 6 数据范围

30 \% n,k \leq 200

$30 \% nkk \leq 10 ^ 740 \% n*k \leq 10 ^ 7对于所有数据,n,k,w[i] \leq 10 ^ 5$

2. 7 样例解释

尽管 OvO 最多可以摘两个Galo,但是最优情况是只摘下第二个点的Galo,
美味度为 10


前置知识

DFS序

dfs序就是一个根据dfs遍历得来的序列,dfs序可以维护一个入栈时间与出栈时间,同时可以维护子树的大小。入栈时间到出栈时间中间的点就是它的子树。并且根据dfs序,遍历时可以保证父亲在儿子前面遍历。

模板代码
//vector<int> node[N];
//int in[N],out[N];
//int Time = 0; //时间戳
void dfs(int now,int fa){
 in[now]=++Time;
 for(int i=0;i<node[now].size();i++)
  if(node[now][i]!=fa) dfs(node[now][i],now);
 out[now]=Time;
}
树上动态规划
树形依赖动态规划

树形依赖动态规划一般为背包问题,依赖就是指儿子依赖于父亲的树形动态规划,一般形式为只有选择了父亲节点才能选择儿子节点,对于这一种特殊的树形动态规划,有一种时间复杂度十分优秀的的方法可以解决此类问题。