Luogu-P2015-二叉苹果树

Posted on 2024-10-01 Edited on 2025-02-24 Word count in article: 728

此篇是本人的一次大胆尝试：一边做题一边写题解！

题目 P2015 二叉苹果树

题目描述

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

这棵树共有 $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$ 是否被访问过。

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
ans = dp[1][Q + 1];

AC Code

// template v8
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 110; // Q

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() {
    // freopen("test.in", "r", stdin);
    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;
}