自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:35:25，当前版本为作者最后更新于2022-08-18 21:17:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树形 DP。

令 $dp_{x}$ 表示以 $x$ 为根的子树的最小质量。设 $L_x$ 为 $x$ 左子节点，$R_x$ 为右子节点，那么 $dp_x = 2 \times \max(dp_{L_x}, dp_{R_x})$。对于一个叶子节点，那么其 dp 值等于该节点的砝码重量。

但这样明显通过不了此题。可以构造数据，使得答案非常大。于是我们可以将 $dp_x$ 的定义改为答案的对数，并且用数组 $pre$ 记录 $dp_x$ 是从哪个节点转移过来的，方便构造方案。我们输出答案则是根据 $pre$ 数组一直往下走，直到找到一个叶子节点为止。设这个叶子结点的质量为 $y$，并且我们走过了 $cnt$ 条边，那么答案便是 $y \times 2 ^ {cnt}$，十分容易用二进制输出。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
using LL = long long;
struct {
    int l, r, v;
} a[N];
bool v[N];
int n, pre[N];
double dfs(int x) {
    double ll, rr;
    if (a[x].l > 0)
        ll = dfs(a[x].l);
    else
        ll = log2(-a[x].l);
    if (a[x].r > 0)
        rr = dfs(a[x].r);
    else
        rr = log2(-a[x].r);
    if (ll > rr)
        pre[x] = a[x].l;
    else
        pre[x] = a[x].r;
    return max(ll, rr) + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].l, &a[i].r);
        if (a[i].l > 0)
            v[a[i].l] = 1;
        if (a[i].r > 0)
            v[a[i].r] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!v[i]) {
            dfs(i);
            int x = i, cnt = 0;
            while (x > 0) {
                x = pre[x];
                ++cnt;
            }
            bool ff = 0;
            x = -x;
            for (int i = 30; i >= 0; --i)
                if (x & 1 << i)
                    printf("1"), ff = 1;
                else if (ff)
                    printf("0");
            for (int i = 1; i <= cnt; ++i) printf("0");
        }
}