题解 - 题解&笔记 - 摘Galo&树形dp与背包

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$），第$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 ^ 7$

$40 \% 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;
}

树上动态规划

树形依赖动态规划

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