Moe's CF Life

喵~ 主にゃん，下午好呀！今天我们来解决一道关于树的构造问题，感觉就像用猫爪搭积木一样有趣呢，嘻嘻。问题是要我们用指定数量的不同类型的节点，搭出一棵高度最小的树。让我们一起来看看怎么才能搭得又快又好吧，喵~

F. 0, 1, 2, Tree!

题目大意 (Problem Summary)

好嘞，听我给你描述一下这个任务，喵~

题目会给我们三个整数 a, b, 和 c。我们需要用这些材料来建造一棵有根树，这棵树必须满足：

有 a 个节点，每个节点恰好有 2 个孩子。
有 b 个节点，每个节点恰好有 1 个孩子。
有 c 个节点，每个节点恰好有 0 个孩子（也就是叶子节点啦，喵~）。

我们的目标是，让这棵树的总高度尽可能地小。所谓高度，就是从根节点到最远的节点的距离（边的数量）。如果能搭成，就输出最小的高度；如果根本不可能用这些材料搭出任何一棵树，就输出 -1。

就像题目里给的例子，a=2, b=1, c=3 可以搭出一棵高度为2的树。我们的任务就是找到这个最小高度，喵~

解题思路 (Solution Approach)

要让树矮一点，直觉上就要让它“胖”一点，对吧？就是说，在靠近根节点的地方，要尽量使用那些能长出更多分叉的节点。这道题里，就是度为2的节点啦。

步骤一：一个神奇的必要条件喵！

在动手搭树之前，我们得先检查一下材料够不够、合不合规矩，不然就是白费力气了，的说~

对于任何一棵树（除了只有一个节点的情况），都有一个非常重要的性质：所有节点的出度之和（也就是孩子数量之和）等于总边数。总边数又等于 总节点数 - 1。

我们有的孩子总数是：2*a + 1*b + 0*c = 2*a + b。
我们有的总节点数是：a + b + c。
所以总边数是：a + b + c - 1。

把它们划上等号： 2*a + b = a + b + c - 1

稍微动动爪子化简一下，就能得到一个非常简洁的式子： a = c - 1 或者说 c = a + 1

这说明，要构成一棵树，叶子节点（c）的数量必须恰好比度为2的节点（a）的数量多1！如果这个条件不满足，那无论怎么搭都不可能成功，我们就可以直接告诉他 “不行！”，然后输出 -1，喵~

步骤二：先搭一个“骨架”树

既然 c = a + 1，我们可以先只用 a 个度为2的节点和 c 个叶子节点来构建一棵树的“骨架”。这正好构成了一个纯二叉树（每个非叶子节点都有2个孩子）。

为了让这棵二叉树的高度最小，我们应该把它搭成一棵尽可能满的、平衡的二叉树，也就是一棵完全二叉树。

那么，用 a 个内部节点能构成的完全二叉树，它的最小高度是多少呢？这个高度 h_a 其实和 a 的二进制表示有关。高度为 h 的完全二叉树，最多可以容纳 2^h - 1 个内部节点。所以，我们需要的高度就是能容纳 a 个内部节点的最小高度。在C++20里，有一个超级方便的函数 std::bit_width(a) 可以直接算出这个值！对于 a=0 的情况，它返回0，也正好对应只有一个节点（c=1）高度为0的树，完美~

所以，我们骨架树的初始高度就是 h_a = std::bit_width(a)。

步骤三：把 `b` 节点塞进去

现在我们有了一个高度为 h_a 的二叉树骨架，接下来要把 b 个度为1的节点给“插入”进去。

怎么插入呢？一个度为1的节点可以插在任意一条边 P -> C 中间，变成 P -> B -> C，这会使 C 以及它下面的所有节点的深度都增加1。

为了不让总高度增加，我们应该优先把这些 b 节点插入到那些“空闲”的位置。什么是空闲位置呢？我们的骨架树高度是 h_a，但它不一定是满的。一棵高度为 h_a 的满二叉树，可以有 2^h_a 个叶子。而我们的骨架只有 a+1 个叶子。

所以，我们有 k = (1LL << h_a) - (a + 1) 个“空位”，可以用来安放 b 节点而不增加树的整体高度 h_a。我们可以安然无恙地塞进去 min(b, k) 个 b 节点。

步骤四：处理剩下的 `b` 节点

如果 b 比 k 还大，那剩下的 b_rem = b - k 个节点就没办法啦，它们一定会增加树的高度。

现在，我们有一棵高度为 h_a 的、被 b 节点填充得满满的树，它有 a+1 个主干分支。我们必须把剩下的 b_rem 个节点均匀地分配到这 a+1 个分支的末端，形成一条条“小尾巴”。

为了让增加的高度最小，我们就要让最长的那条“小尾巴”尽可能短。这不就是经典的分配问题嘛！把 b_rem 个东西分到 a+1 个篮子里，让最多的篮子里的东西数量最小。这个数量就是 ceil(b_rem / (a + 1))。

这个增加的高度 h_b 就是 (b_rem + a) / (a + 1)（这是整数向上取整的小技巧哦）。

最终高度

所以，最终的最小高度就是骨架高度 h_a 加上因为塞不下的 b 节点而增加的高度 h_b。 Total Height = h_a + h_b

搞定收工，喵呜~

题解代码 (Solution Code)

这是解法的C++代码，我已经加上了一些可爱的注释，喵~

cpp

#include <iostream>
#include <numeric>
#include <algorithm>
#include <bit>

void solve() {
    long long a, b, c;
    std::cin >> a >> b >> c;

    // 步骤一：检查魔法条件，喵~
    // 叶子节点c的数量必须比度为2的节点a的数量多1
    if (a + 1 != c) {
        std::cout << -1 << "\n";
        return;
    }

    // 如果a=0, c=1，树就是一条直线，高度就是b
    // 我们的公式也能处理这种情况，这里就不特殊判断了，喵~
    if (a == 0 && c == 1) {
        // b=0时高度为0，b>0时高度为b
        std::cout << b << "\n";
        return;
    }

    // 步骤二：计算纯二叉树骨架的最小高度
    long long da = std::bit_width((unsigned long long)a);

    // 步骤三：计算不增加高度就能塞下的b节点的数量k
    // 一棵高度为da的二叉树最多能有 2^da 个叶子
    // 我们已经用了 a+1 个，剩下的就是空位啦
    long long k = (1LL << da) - a - 1;

    long long height = da;
    
    // 步骤四：如果b节点比空位还多，就要增加高度了
    if (b > k) {
        long long b_rem = b - k;
        // 把剩下的b_rem个节点，均匀地分配到 a+1 个分支上
        // 增加的高度就是 ceil(b_rem / (a+1))
        long long db = (b_rem + a) / (a + 1); // 整数向上取整的写法
        height += db;
    }

    std::cout << height << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F. 0, 1, 2, Tree! ​

题目大意 (Problem Summary) ​

解题思路 (Solution Approach) ​

步骤一：一个神奇的必要条件喵！ ​

步骤二：先搭一个“骨架”树 ​

步骤三：把 b 节点塞进去 ​

步骤四：处理剩下的 b 节点 ​

最终高度 ​

题解代码 (Solution Code) ​

相关知识点 (Knowledge Points) ​