大家好，我是非（欧）洲人michaeljack（tonyfang)；这节课我们来讲讲怎么搞基（学习）。

今天来讲的是一类有依赖性的树形dp问题

最著名的就是选课啦！Codevs1378

嗯然后我们讲讲普通的树形dp如何实现。

$f_{i,j}$表示以$i$为根的子树中，必须选$i$，而且选$j$个课的最大价值

然后我们发现，转移懵逼？！

$f_{i,j} = \sum_{i=1}^{son_{i}}f_{i, d_{i}}$，其中$\sum_{i=1}^{son_{i}} d_{i} = j$

啊这怎么枚举啊？黑人问号*n。

当然要用背包啦！设$g_{i,j}$表示当前这个节点前$i$棵子树，选了$j$个课的最大价值。

那么我们就可以这么写啦$g_{i,j} = max(g_{i,j}, g_{i, j-k} + f_{son[i], k})$。

然后转移就很简单啦$f_{i,j} = g_{i, j-1} + w_{i}$，复杂度可以证明是$O(nm)$

嗯这就做完啦！

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int n, m;
int fa[510], w[510], f[510][510], g[510][510], size[510];
int head[510], next[200010], to[200010], tot;
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dp(int x, int father) {
	size[x]=1; int as = 0;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		dp(to[i], x);
		size[x]+=size[to[i]];
		++as;
	}
	int j=0, To = min(m, size[x]);
	for (int i=0; i<=as; ++i)
		for (int k=1; k<=To; ++k) g[i][k]=0;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		++j;
		for (int k=1; k<=To; ++k)
			for (int ch=0; ch<=k; ++ch)
				g[j][k] = max(g[j][k], g[j-1][k-ch] + f[to[i]][ch]);
	}
	for (int i=1; i<=To+1; ++i)
		f[x][i] = max(f[x][i], g[j][i-1]+w[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) {
		scanf("%d%d", &fa[i], &w[i]);
		add(i, fa[i]);
		add(fa[i], i);
	}
	dp(0, -1);
	//for (int i=0; i<=n; ++i) 
	//	for (int j=1; j<=m; ++j)
	//		printf("i=%d, j=%d, f[i][j]=%d\n", i, j, f[i][j]);
	printf("%d\n", f[0][m+1]);
	return 0;
}

当然接下来才是本文重点，用dfs序来处理！

“首先我们处理出这个树的dfs序，然后我们乱搞就行了啊！”

“怎么乱搞啊？黑人问号*n”

嗯首先dfs序内子树一定是连续的一段区间，那么我们可以设$f[i, j]$表示以第i个点及以后的dfs序的大小为j的连通块的最大权值，那么我们就可以转移啦！

$f_{i,j} = max(f_{i+size[x], j}, f_{i+1, j-1}+w_{x})$

就没啦！

p.s 多叉树转二叉树的奇妙方法

把多叉树先转化成“左儿子，右兄弟”的表示方法。会发现形成这样一种结构图：多叉树：

转化成“左儿子，右兄弟”的二叉树：

# include <stdio.h>
# include <algorithm>
using namespace std;

int dfn[510], ndfn[510], n, m, w[510], idfn = 0;
int size[510];
int head[510], next[200010], to[200010], tot, f[510][510];
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int father) {
	size[x]=1; dfn[x] = ++idfn; ndfn[idfn]=x;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		dfs(to[i], x);
		size[x]+=size[to[i]];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1, fa; i<=n; ++i) {
		scanf("%d%d", &fa, &w[i]);
		add(i, fa);
		add(fa, i);
	}
	dfs(0, -1);
	for (int i=n+1; i>=1; --i) {
		int x = ndfn[i];
		for (int j=1; j<=m+1; ++j) 
			f[i][j] = max(f[i+size[x]][j], f[i+1][j-1]+w[x]);		
	}
	printf("%d\n", f[1][m+1]);
	return 0;
}