2. 摘 Galo(OvO) 1s/512M
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），第i个 Galo 美味度为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;
}
树上动态规划
树形依赖动态规划
树形依赖动态规划一般为背包问题，依赖就是指儿子依赖于父亲的树形动态规划，一般形式为只有选择了父亲节点才能选择儿子节点，对于这一种特殊的树形动态规划，有一种时间复杂度十分优秀的的方法可以解决此类问题。
正文完
