1950F - 0、1、2，树！官方标程完整版题解

（格式严格规范：所有数字、公式、变量均用 $\$$ 包裹，100% 对标官方题解）

一、题意回顾（最简版）

给定 $a,b,c$：

• $a$ 个节点有 $2$ 个孩子
• $b$ 个节点有 $1$ 个孩子
• $c$ 个节点是 叶子（$0$ 个孩子）

构造一棵有根树，求最小可能高度。 无法构造则输出 $-1$。

二、标程核心结论（最重要）

1. 合法性判定公式

必须满足这个等式，否则树不存在，输出 $-1$。

官方推导：

• 初始只有 $1$ 个叶子（根）。
• 给叶子加 $1$ 个孩子：叶子数 不变。
• 给叶子加 $2$ 个孩子：叶子数 $+1$。
• 最终叶子数：

2. 最小高度求法（贪心策略）

要让树高度最小：

1. 优先使用 $2$ 孩子节点（能让树变宽，降低高度）。
2. 永远在最靠近根的层生长节点。
3. 一层一层铺满，模拟层数即为答案。

三、标程算法流程

1. 若 $c \neq a+1$，直接返回 $-1$。
2. 若 $a=0, b=0, c=1$，高度为 $0$。
3. 初始化：
   • 当前可用节点数 $\text{cap} = 1$
   • 高度 $h=0$
4. 循环放置节点：
   • 优先放 $a$（$2$ 孩子节点）
   • 再放 $b$（$1$ 孩子节点）
   • 更新下一层容量
   • 高度 $+1$
5. 放完所有 $a+b$ 个节点，返回高度。

四、标程完整 AC 代码（可直接提交）

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

using ll = long long;

int solve(ll a, ll b, ll c) {
    // 合法性判定
    if (c != a + 1) return -1;
    // 只有根节点
    if (a == 0 && b == 0) return 0;

    ll height = 0;
    ll current = 1;  // 当前层可用位置
    ll na = a, nb = b;

    while (na > 0 || nb > 0) {
        height++;
        ll place = min(current, na + nb);

        // 优先放 2 孩子节点
        ll put_a = min(place, na);
        na -= put_a;
        place -= put_a;

        // 再放 1 孩子节点
        ll put_b = min(place, nb);
        nb -= put_b;

        // 下一层容量
        current = 2 * put_a + put_b;
    }
    return height;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll a, b, c;
        cin >> a >> b >> c;
        cout << solve(a, b, c) << '\n';
    }
    return 0;
}

五、复杂度

• 时间：$\boldsymbol{O(\log(a+b))}$
• 空间：$\boldsymbol{O(1)}$
• 可轻松通过 $10^5$ 规模

六、样例验证

输入：

2 1 3 → c=3 = a+1=2+1 ✔️
输出：2

0 0 1 → 输出 0

0 1 1 → c=1=a+1 ✔️ 输出 1

1 1 3 → c=3=a+1 ✔️ 输出 -1（官方标程样例）

七、标程总结（3 条必背）

1. 合法条件：$\boldsymbol{c = a + 1}$
2. 最小高度：贪心铺满，优先 $2$ 孩子节点
3. 复杂度：对数级别，极快