二叉苹果树——树形Dp（由根到左右子树的转移）
题意：给出一个二叉树，每条边上有一定的边权，并且剪掉一些树枝，求留下 Q 条树枝的最大边权和。 （ 节点数 n ≤100，留下的枝条树 Q ≤ n ，所有边权和 ∑w[i] ≤30000 ）
细节：对于一棵子树 u 来说如果剪掉 u 节点上方的树枝，则该子树内的所有树枝都相当于被剪去。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。分析：由于是二叉树，所以转移就与左右子树有关，其次我们需要求出最大的边权和，而且需要记录当前子树保留了多少枝条。
所以 Dp 的状态：dp[u][j] 表示以 u 为根保留了 j 条树枝（包括 u 的前一条树枝）
转移： dp[u][j] = max( dp[lx[u]][k] + dp[ly[u]][j-k-1] + Pre[u], dp[u][j] ) lx[u]表示 u 的左子树，ly[u]表示 u 的右子树，Pre[u]表示 u 的前一条边
（ j≤size[u]，k≤min( size[lx[u]] , j-1) ）size[u]表示以 u 为子树的节点个数
代码如下：
#include <bits/stdc++.h>
#define MAXN 105
using namespace std; struct edge{ int to, Next, val; }Right[MAXN<<1]; int Begin[MAXN], f[MAXN][MAXN], Pre[MAXN], size[MAXN], n, q, cnt, lx[MAXN], ly[MAXN]; inline void add_edge(int x, int y, int z){ Right[++cnt].to=y; Right[cnt].Next=Begin[x]; Begin[x]=cnt; Right[cnt].val=z; } void build(int u, int fa){ size[u]=1; for (int i=Begin[u]; i; i=Right[i].Next){ int v=Right[i].to; if (v==fa) continue; Pre[v]=Right[i].val; if (!lx[u]) lx[u]=v; else ly[u]=v; build(v, u); size[u]+=size[v]; } } void solve(int u, int fa){ for (int i=Begin[u]; i; i=Right[i].Next){ int v=Right[i].to; if (v==fa) continue; solve(v, u); for (int j=2; j<=size[u]; j++) for (int k=0; k<=min(size[lx[u]], j-1); k++) f[u][j]=max(f[u][j], f[lx[u]][k]+f[ly[u]][j-k-1]+Pre[u]); } } int main(){ scanf("%d%d", &n, &q); for (int i=1; i<n; i++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); add_edge(x, y, z); add_edge(y, x, z); } build(1, 0); for (int i=1; i<=n; i++) f[i][1]=Pre[i]; solve(1, 0); printf("%d\n", f[1][q+1]); return 0; }
更多精彩
