信息学奥赛一本通 1575：【例 1】二叉苹果树 | 洛谷 P2015 二叉苹果树

【题目链接】

ybt 1575：【例 1】二叉苹果树
洛谷 P2015 二叉苹果树

【题目考点】

1. 树形动规

• 有依赖的背包

【解题思路】

解法1：建立二叉树 树形动规

树枝为边，苹果数量为边权。

• 阶段：以结点u为根的子树 保留j条边
• 决策：保留哪些边
• 策略：留下的子树
• 策略集合：以结点i为根的子树保留j条边能得到的所有子树
• 条件：边权加和最大
• 统计量：边权加和

状态定义：$d{p}_{u,j}$：以结点u为根结点的子树中，保留j条边能获得的最大的边权加和。
状态转移：根据结点u的左右子树各分到多少条边来分割策略集合。
设结点u的左孩子为l，右孩子为r。边(u,l)的权值为$w_{u,l}$，边(u,r)的权值为$w_{u,r}$。

• 情况1：只在左子树选边，首先要选边(u,l)，而后要在以l为根结点的子树中选择j-1条边，得到的最大边权加和为$d{p}_{l,j-1}+w_{u,l}$
• 情况2：只在右子树选边，首先要选边(u,r)，而后要在以r为根结点的子树中选择j-1条边，得到的最大边权加和为$d{p}_{r,j-1}+w_{u,r}$
• 情况3：左右子树都选边，首先要选择边(u,l)与(u,r)，而后还剩下j-2条边。
  假设分配给左子树$k$条边，那么要分配给右子树$j-2-k$条边。$k$最小为0，最大为$j-2$。
  要在以l为根结点的子树中选择$k$条边，能获得的最大边权加和为$d{p}_{l,k}$
  在以r为根结点的子树中选择$j-2-k$条边，能获得的最大边权加和为$d{p}_{r,j-2-k}$。
  总边权加和为$d{p}_{l,k}+d{p}_{r,j-2-k}+w_{u,l}+w_{u,r}$
  以上多种情况求最大值。
  dpu,j=max⁡{dpl,j−1+wu,l,dpr,j−1+wu,r,max⁡0≤k≤j−2−k{dpl,k+dpr,j−2−k+wu,l+wu,r}}dp_{u,j} = \max\{dp_{l, j-1}+w_{u,l}, dp_{r, j-1}+w_{u,r}, \underset{0\le k \le j-2-k}\max\{dp_{l,k}+dp_{r,j-2-k}+w_{u,l}+w_{u,r}\}\}dpu,j​=max{dpl,j−1​+wu,l​,dpr,j−1​+wu,r​,0≤k≤j−2−kmax​{dpl,k​+dpr,j−2−k​+wu,l​+wu,r​}}

先把所有的边保存到邻接表。
深搜过程中，先将当前结点u的不是父结点的两个邻接点确定哪个是左孩子，哪个是右孩子。左孩子设为l，u到l的边权设为lw。右孩子设为r，u到r的边权设为rw。
在循环遍历u的孩子，完成对子结点是搜索后，再尝试求$d{p}_{u,j}，1\le j\le q$，q是输入要保留的总边数。

根是1号结点，从根结点出发进行树形动规，最后$d{p}_{1,q}$就是结果。

解法2：有依赖的背包

状态定义：$d{p}_{u,i,j}$：以u为根的树中前i个子树保留j条边（包括和u连接的边）能够得到的最大权值加和。
状态转移方程：
策略集合：以u为根的树中前i个子树保留j条边的所有方案
分割策略集合：根据第i个子树保留几条边来分割策略集合
前i-1个子树保留j-k条边，能获得的最大权值加和为$d{p}_{u,i-1,j-k}$。
第i个子树保留k条边。边(u,v)的权值为$w_{u,v}$。第i个子树的根结点为v，以v为根的子树的前2个子树（由于是二叉树）。能获得的最大权值加和为$d{p}_{v,2,k-1}+w_{u,v}$
保留k-1条边。k最小为1，最大为j。
dpu,i,j=max⁡1≤k≤j{dpu,i−1,j−k+dpv,2,k−1+wu,v}dp_{u,i,j} = \underset{1\le k \le j}\max\{dp_{u,i-1,j-k}+dp_{v,2,k-1}+w_{u,v}\}dpu,i,j​=1≤k≤jmax​{dpu,i−1,j−k​+dpv,2,k−1​+wu,v​}
可以进行滚动数组优化，优化掉第二维i，得到：
dpu,j=max⁡1≤k≤j{dpu,j−k+dpv,k−1+wu,v}dp_{u,j} = \underset{1\le k \le j}\max\{dp_{u,j-k}+dp_{v,k-1}+w_{u,v}\}dpu,j​=1≤k≤jmax​{dpu,j−k​+dpv,k−1​+wu,v​}
如果本题是多叉树，使用有依赖的背包方法，也可以解决。

【题解代码】

解法1：树形动规 二叉树

#include <bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{int v, w;
};
vector<Edge> edge[N];
int n, q, dp[N][N];//dp[i][j]：以i为根的树中保留j条边能够得到的最大边权加和
void dfs(int u, int fa)
{int l = 0, r = 0, lw, rw;if(edge[u].size() == 1)//叶子结点 return;for(Edge e : edge[u]){int v = e.v, w = e.w;if(v != fa){if(l == 0)l = v, lw = w;else r = v, rw = w;dfs(v, u);}}for(int j = 1; j <= q; ++j){dp[u][j] = max(lw+dp[l][j-1], rw+dp[r][j-1]);//左子树或右子树完全没有的情况。 for(int k = 0; k <= j-2; ++k)//同时有左右子树，左子树保留k条边dp[u][j] = max(dp[u][j], lw+rw+dp[l][k]+dp[r][j-2-k]);}
} 
int main()
{int f, t, w;cin >> n >> q;for(int i = 1; i < n; ++i){cin >> f >> t >> w;edge[f].push_back(Edge{t, w});edge[t].push_back(Edge{f, w});}dfs(1, 0);cout << dp[1][q];return 0;
}

解法2：树形动规 有依赖的背包

#include <bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{int v, w;
};
vector<Edge> edge[N];
int n, q, dp[N][N];//dp[u][i][j]：以u为根的树中前i个子树保留j条边（包括和u连接的边）能够得到的最大权值加和
void dfs(int u, int fa)
{for(Edge e : edge[u]){int v = e.v, w = e.w;if(v != fa){dfs(v, u); for(int j = q; j >= 1; --j)for(int k = 1; k <= j; ++k)//一定包含u到v的边 子树v保留k-1条边 dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[v][k-1]+w);}}
} 
int main()
{int f, t, w;cin >> n >> q;for(int i = 1; i < n; ++i){cin >> f >> t >> w;edge[f].push_back(Edge{t, w});edge[t].push_back(Edge{f, w});}dfs(1, 0);cout << dp[1][q]; return 0;
}