题解 | #种树#

这是一个经典的树上最优化问题，结合了二分答案与树形动态规划（Tree DP）。

一、 问题分析

1. 树结构特征：

   • 题目描述了一棵满二叉树结构，即树中的每个节点通常被称为“内部节点”（有两个子节点）或“叶子节点”（无子节点）。
   • 初始时，只有原始叶子节点的生命力数值是有效的决策依据。尽管输入给出了所有节点的权值，但根据规则“剪枝后 变成叶子节点”，内部节点的初始值会被子节点在其修剪时产生的新值覆盖，因此内部节点的输入权值可忽略。

2. 操作本质：

   • 这是一个自底向上的计算过程。
   • 大园林剪：相当于逻辑运算 ，消耗 1 次“大剪”额度。
   • 小园林剪：相当于逻辑运算 ，不消耗“大剪”额度（或者说消耗“小剪”额度）。

3. 资源约束：

   • 设内部节点总数为 。
   • 我们拥有的“大园林剪”最大使用次数为 。
   • 在满二叉树中，若叶子节点数为 ，则内部节点数 。因此可用的大剪次数约为叶子节点总数的一半。

4. 优化目标：

   • 最大化根节点最终的生命力。

二、 算法：二分答案 + 树形 DP

直接计算根节点最大值的复杂度极高，因为涉及操作序列的组合。然而，如果我们假设一个目标值 ，验证“根节点的值能否 ”则相对容易。

这一性质满足单调性：如果根节点能达到值 ，那么它一定能达到所有小于 的值。这决定了我们可以使用二分答案。

1. 二分答案

我们将问题转化为判定性问题：“能否使用不超过 次大园林剪，使得根节点的最终生命力 ？”

• 二分范围： 或将所有叶子节点的权值离散化后的下标范围 。

2. 检查函数 Check(mid) 的设计 (Tree DP)

在判定过程中，我们需要计算：为了让节点 的值 ，在以 为根的子树中，最少需要消耗多少次“大园林剪”？

定义状态 为：使节点 的权值 所需的最少大园林剪次数。

• 基本情况（叶子节点）：

  • 若 ，则 （无需任何操作即可满足）。
  • 若 ，则 （该节点本身无法达标，设为一个很大的数，如 ）。

• 状态转移（内部节点 ，左右儿子 ）： 想要 达标，我们有两种策略：

  1. 使用大园林剪 (Max)：
     • 规则：。
     • 条件：只要左儿子或右儿子其中之一达标即可。
     • 代价：当前消耗 1 次 + 子树最小代价。
     • 转移：。
  2. 使用小园林剪 (Min)：

     • 规则：。

     • 条件：左儿子和右儿子必须同时达标。

     • 代价：当前消耗 0 次 + 左右子树代价之和。

     • 转移：。

  • 最终决策：由于我们希望消耗的大剪次数最少，故取两者的最小值：

• 判定结论：

  • 计算至根节点后，如果 ，则说明目标值 是可行的 (True)。
  • 否则，说明为了达到 ，需要的大剪次数超过了限制， 不可行 (False)。

三、 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = 1e5 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<bool> parent(n + 1, false);
    vector<int> ls(n + 1), rs(n + 1);

    int m = 0;
    for (int i = 1; i <= n; i++) {
        cin >> ls[i] >> rs[i];
        if (ls[i] > 0)
            parent[ls[i]] = true;
        if (rs[i] > 0)
            parent[rs[i]] = true;
        if (ls[i] > 0 && rs[i] > 0)
            m++;
    }

    vector<ll> leaves;
    vector<ll> val(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        if (ls[i] == 0 && rs[i] == 0) {
            leaves.push_back(val[i]);
        }
    }

    sort(leaves.begin(), leaves.end());
    leaves.erase(unique(leaves.begin(), leaves.end()), leaves.end());

    auto getMinCost = [&](auto&& self, int u, ll target) -> ll {
        if (ls[u] == 0 && rs[u] == 0) {
            return val[u] >= target ? 0 : INF;
        }

        ll leftCost = self(self, ls[u], target);
        ll rightCost = self(self, rs[u], target);

        ll costMin = leftCost + rightCost;
        costMin = min(costMin, INF);

        ll costMax = 1 + min(leftCost, rightCost);
        costMax = min(costMax, INF);

        return min(costMin, costMax);
    };

    int k = (m + 1) / 2;
    auto check = [&](ll x) -> bool {
        int needed = getMinCost(getMinCost, 1, x);
        return needed <= k;
    };

    int l = 0;
    int r = leaves.size() - 1;
    ll ans = leaves[0];

    while (l <= r) {
        int mid = l + (r - l) / 2;
        ll midVal = leaves[mid];

        if (check(midVal)) {
            ans = midVal;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << endl;
}

四、 复杂度与权衡分析

1. 时间复杂度：

   • 二分搜索：需要进行 次检查。如果离散化权值，则是 。
   • Check 函数：每次检查通过 DFS 遍历整棵树，复杂度为 ，其中 是节点总数。
   • 总复杂度：（假设权值离散化或值域合理）。

2. 空间复杂度：

   • 需要存储树结构和节点权值：。
   • 递归调用栈深度：最坏情况 （链状），但题目为满二叉树，通常深度为 ，即使退化也是线性的。
   • 总空间复杂度：。

3. 鲁棒性与边界条件：

   • 的处理：在代码实现中，无穷大应定义为一个大于 的数（例如 或 ）即可，避免使用 INT_MAX 导致加法溢出。
   • 叶子判断：必须准确判断节点是否有子节点（ 且 ），切勿对内部节点应用基准判断逻辑。
   • 输入值处理：只关心叶子节点的初始权值。

总结

该算法的核心在于将“最大化数值”问题通过二分法转化为“满足数值所需的最小代价”问题。通过树形 DP 贪心地在每个节点选择消耗代价最小的剪枝策略（是消耗一次本身换取对子节点要求的降低，还是不消耗本身但要求子节点全部达标），从而求出全局最优解。