CF161D Distance in Tree + 树上背包

油爆虾

CF161D Distance in Tree

DP状态定义

根据子树位置\(+\)路径长度的统计设计状态。

\(Dp_{u,j}\)表示在以 \(u\) 为根的子树中，到 \(u\) 的距离恰好为 \(j\) 的节点个数。

初始化

\[dp_{u, 0}=1 \]

状态转移方程式

在合并子树时来统计答案

\[ans = ans + \sum^k_{j=0}dp_{u,j} \times dp_{j,k-1-j} \]

处理完答案后再合并子树：

\[dp_{u,j}=dp_{u,j}\sum^k_{j=1}dp_{v,j-1} \]

戳我看代码

void dfs(int u, int fa) {
	dp[0] = 1;
	for (auto v : g) {
		if (fa == v) continue;
		dfs(v, u);
		rep(j, 0, k - 1) ans += dp[j] * dp[v][k - 1 - j];
		rep(j, 1, k) dp[j] += dp[v][j - 1];
	}
}

最重要的，树上背包！

例题：[CTSC1997] 选课

状态定义

\(dp_{u,i,j}\)表示在 \(u\) 这里，前 \(i\) 棵子树，共计选择 \(j\) 门课，共可以获得的最大贡献。

状态转移

自己先想想，很简单，或者看代码。

戳我看代码

void dfs(int u){
	for(auto v:graph){
		dfs(v); // 先递归求出子树的答案
	}
	
	dp[0][1] = score;
	for(int i=1;i<=graph.size();i++){
		int v=graph[i-1];
		int siz_v=graph[v].size(); // 标记1
		for(int j=1;j<=m+1;j++){ // 至少选自己这门课，才可以考虑子树
			dp[j]=dp[i-1][j]; // 不选 v 子树，直接继承。
			// 选 v 子树，枚举选多少
			for(int k=0;k<=m+1;k++) if(j>k){//至少选自己这门课，才可以考虑子树
				dp[j]=max(dp[j],dp[i-1][j-k]+dp[v][siz_v][k])
			}
		}
	}
}

来源：https://www.cnblogs.com/sPERbEETLE/p/19576287