P2015 二叉苹果树

P2015 二叉苹果树
类似于带限制背包问题，但不知道也能做。
$n,q$ 范围小，大胆设 dp 状态。设 $f_{u,i}$ 表示 $u$ 子树内保留 $i$ 根树枝的最大苹果数，可得状态转移方程 $f_{u,i}=f_{u,j}+f_{v,i-j-1}+w$，其中 $w$ 指连接 $u,v$ 的树枝上的苹果数，$i-j-1$ 而非 $i-j$ 在于 $u,v$ 这条边占了一根树枝。注意此时的 $f_{u,j}$ 不能包含当前 $v$ 所在的子树，原因很显然，同一个子树上的树枝不能被计算两次。

列完转移方程注意边界和外层循环。边界 $f_{u.0}=0$，因为转移时 $f_{u,i}$ 调用的 $f_{u,j}$ 不能包含当前 $v$ 所在的子树，所以应将 $i$ 从大到小转移。

时间复杂度 $O(n{q}^2)$。

在这里插入代码片#include<bits/stdc++.h>
using namespace std;
int n,q,p[105],f[105][105];
struct qh{int v,w,nt;
}E[205];
void add(int u,int v,int w){E[++p[0]]=(qh){v,w,p[u]};p[u]=p[0];return ;}
void dfs(int u,int fa){for(int i=p[u];i;i=E[i].nt){int v=E[i].v;if(v==fa) continue;dfs(v,u);for(int j=q;j>=1;j--) for(int k=0;k<=j-1;k++) f[u][j]=max(f[u][j],f[u][k]+f[v][j-k-1]+E[i].w);}return ;
}
int main(){scanf("%d%d",&n,&q);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}dfs(1,0);printf("%d",f[1][q]);return 0;
}
/*
start coding:18:47
finish debuging:19:03
*/

---

附上题目：

二叉苹果树

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1\sim N$，树根编号一定是 $1$。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：

2   5\ / 3   4\ /1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

输入格式

第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。

接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。

输出格式

一个数，最多能留住的苹果的数量。

样例 #1

样例输入 #1

5 2
1 3 1
1 4 10
2 3 20
3 5 20

样例输出 #1

21

提示

$1⩽Q<N⩽100$，每根树枝上的苹果 $⩽3\times 10^4$。