题解：P3874 [TJOI2010] 砍树

no1dea · 2026-10-22 21:16:08 · 题解

题记：想练习二分题的笨比看到“砍树”就急头白脸地写成了这个。

思路

首先审题：最明显的两个算法特征就是树和背包了，那么就想到是一道树形背包的题。

同时最后求的是平均值：

（默认所选节点的总权重为正。）

所以就可以想到二分答案。每次固定一个 \lambda，把每个节点的价值改成 v_i-\lambda w_i，然后判断是否存在一个满足题目要求的连通子树，使得总分大于等于 0。

首先，单纯 DFS 暴力搜肯定是不太可能的，这个题目得用背包 DP 的方式。

但是既然是在树上，剪下的节点又不能断开，那么为什么不让树的每一个节点都向下长出一个子树呢？

我的想法是，设

表示以 u 为根、选择一个包含 u 且恰好有 cnt 个节点的连通子树时，能得到的最大变换后总分。

这样每个节点都可以作为一个起点。无论最后选择的连通子树位于哪里，都可以找到它相对于 DFS 根的最高点，所以不会因为只从第一个节点开始搜索而漏掉答案。

抽象来说，就像是把树从第一个点开始向下按连接关系排布（向下捋？x），树的每个点上又都可以向下长出一棵以自己为根的子树。

那么要如何实现在有不同子节点，且子节点的不同长度有不同最优方案的情况下取得全局最佳方案呢？

这时候就可以考虑树形背包。

首先只选当前节点自己：

然后逐个合并子节点。假设当前已经选了 x 个节点，再从子节点 v 的子树中选出 y 个节点，那么：

一开始我还想过把 DP 数组升级成三维：

dp[选了几个节点][起始节点是哪个][当前合并到哪个子节点]

但是这样感觉有点麻烦，而且我本来也不太喜欢三维以上的数组 awa

所以我选择每次复制一个当前状态的副本，用副本计算，避免在同一轮合并中重复使用当前子节点刚刚更新出来的状态。

也就是用 cur 保存当前已经合并完部分子节点的状态，用 nxt 保存加入当前子节点后的状态。计算完成后再令 cur=nxt。

最后，每次二分一个 m，重新计算所有节点的变换后价值：

再进行树形 DP，检查是否存在一个大小至少为 k 的连通子树，使得总分大于等于 0。

如果存在，就说明当前 m 可行，令 l=m；否则令 r=m。

不断二分，直到区间长度足够小，最后输出答案即可。

代码

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

struct pot {
    double value;
    int weight;
    vector<int> branch;
};

int n, k;
pot tree[101];
double dp[101][101]; // 第几个节点、选取多少个节点
double m, l, r;

// function area

void DFS_tree(int pos, int root, int num)
{
    for (int i = 0; i < tree[pos].branch.size(); i++)
    {
        if (tree[pos].branch[i] == root) continue;
        DFS_tree(tree[pos].branch[i], pos, num);
    }

    vector<double> cur(num + 1, -1e18);
    cur[1] = dp[1][pos];

    for (int i = 0; i < tree[pos].branch.size(); i++)
    {
        int c = tree[pos].branch[i];
        if (c == root) continue;

        vector<double> nxt = cur;

        for (int t = 2; t <= num; t++)
        {
            for (int s = 1; s <= t - 1; s++)
            {
                if (dp[s][c] <= -1e17 ||
                    cur[t - s] <= -1e17)
                    continue;

                nxt[t] = max(nxt[t],
                             cur[t - s] + dp[s][c]);
            }
        }

        cur = nxt;
    }

    dp[num][pos] = cur[num];
}

bool check()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = k; j <= n; j++)
        {
            if (dp[j][i] >= 0)
                return true;
        }
    }

    return false;
}

int main()
{
    l = 0;

    for (int i = 0; i <= 100; i++)
    {
        for (int j = 0; j <= 100; j++)
        {
            dp[i][j] = -1e18;
        }
    }

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> tree[i].value;
        r = max(r, tree[i].value);
    }

    for (int i = 1; i <= n; i++)
    {
        cin >> tree[i].weight;
    }

    for (int i = 1; i < n; i++)
    {
        int a1, a2;
        cin >> a1 >> a2;

        tree[a1].branch.push_back(a2);
        tree[a2].branch.push_back(a1);
    }

    while (r - l > 1e-6)
    {
        m = (l + r) / 2.0;

        for (int i = 1; i <= n; i++)
        {
            dp[1][i] =
                tree[i].value - tree[i].weight * m;
        }

        for (int i = 2; i <= n; i++)
        {
            DFS_tree(1, 0, i);
        }

        if (check())
            l = m;
        else
            r = m;
    }

    cout << fixed << setprecision(2) << m << '\n';
}

总结

这道题一开始只是想练习二分，结果看到“砍树”就开始往树形背包的方向想了。

第一个题解记录一下，复杂度比不上题解区里其他大佬，但是也许应该可能更通俗一点？（qwq）。