此篇是本人的一次大胆尝试：一边做题一边写题解！
题目描述
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。
接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。
输出格式
一个数，最多能留住的苹果的数量。
思路：树形dp
既然是跟树相关，那肯定是树形dp啦！
边点转化
不难发现，一条边被删除和这条边对应的子节点被删除是等价的。
所以不妨把边的苹果数量转化为子节点上的苹果数量。
基本定义
$dp[i][j]$ 表示 $i$ 节点上保留 $j$ 个节点的最大苹果数。
$son[i][0/1]$ 表示 $i$ 的左右儿子。
$apple[i]$ 表示节点 $i$ 上的苹果数量。
$son_node[i]$ 表示节点 $i$ 的子节点数量（含自身）。
建树
本题的建树较为特殊。因为在输入一条边时，无法确定哪个点是父节点（绝对不是我卡在这很长时间）。
所以先用邻接矩阵存储每一条边，之后从根节点 $1$ 出发，获取每条边对应的另一个节点即为子节点。
使用 $vis[i]$ 记录节点 $i$ 是否被访问过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| struct node{
int to, apple;
};
vector<node> arr[N];
void init(int f) {
if(vis[f]){
for(node n : arr[f]){
if(vis[n.to]) continue;
son[f][(bool)(son[f][0])] = n.to;
apple[n.to] = n.apple;
vis[n.to] = true;
init(n.to);
}
}
son_node[f] = son_node[son[f][0]] + son_node[son[f][1]] + 1;
}
int main(){
vis[1] = true;
init(1);
}
|
状态
- 初状态：每个最深子节点上保留/舍弃自身的状态已知。
想获取最深子节点，每次搜索到最深处不太合理，所以使用队列，从子节点一层层深入，同时记录当前节点。
1
2
3
4
5
6
7
| queue<int> q;
void init(int f){
son_node[f] = son_node[son[f][0]] + son_node[son[f][1]] + 1;
q.push(f);
}
|
以上可看作树的后序遍历。
如果 $son_node[x]$ 为 $1$，即只有自己这个节点，那么 $x$ 就是最深层的子节点。
1
2
3
4
5
| if(son_node[x] == 1) {
dp[x][0] = 0;
dp[x][1] = apple[x];
continue;
}
|
首先，一个节点 $x$ 有左子树和右子树。
如果左子树保留 $i$ 个节点，右子树保留 $j$ 个节点，那么 $x$ 就含有 $i+j+1$ 个节点（含自身）。
所以，状态转移方程如下。
1
| dp[x][i + j + 1] = max(dp[x][i + j + 1], dp[son[x][0]][i] + dp[son[x][1]][j] + apple[x]);
|
注：今后不再使用minset/maxset。
- 末状态：节点 $1$ 上保留 $Q$ 个节点的苹果数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x7f7f7f7f;
const int N = 110;
int dp[N][N];
int son[N][2];
int son_node[N];
int apple[N];
bool vis[N];
int n, Q;
queue<int> q;
struct node{
int to, apple;
};
vector<node> arr[N];
void init(int f) {
if(vis[f]){
for(node n : arr[f]){
if(vis[n.to]) continue;
son[f][(bool)(son[f][0])] = n.to;
apple[n.to] = n.apple;
vis[n.to] = true;
init(n.to);
}
}
son_node[f] = son_node[son[f][0]] + son_node[son[f][1]] + 1;
q.push(f);
}
int main() {
cin >> n >> Q;
int t1, t2, t3;
for(int i = 0; i < n - 1; i++) {
cin >> t1 >> t2 >> t3;
arr[t1].push_back({t2, t3});
arr[t2].push_back({t1, t3});
}
vis[1] = true;
init(1);
while(q.size()) {
int x = q.front();
q.pop();
if(son_node[x] == 1) {
dp[x][0] = 0;
dp[x][1] = apple[x];
continue;
}
for(int i = 0; i <= son_node[son[x][0]]; i++) {
for(int j = 0; j <= son_node[son[x][1]]; j++) {
dp[x][i + j + 1] = max(dp[x][i + j + 1], dp[son[x][0]][i] + dp[son[x][1]][j] + apple[x]);
}
}
}
cout << dp[1][Q + 1] << endl;
return 0;
}
|