P11206 「Cfz Round 9」Dove 题解

· · 题解

题意简述

给定一棵树，希望给其上的所有点编号，使得所有边的两端端点编号之和均不超过 N+1。

分析

可以使用如下的贪心策略进行编号：

接下来，我们对这个策略的正确性进行一个简要的证明。

使用数学归纳法。我们称在一个拥有 N 个节点的子树上，使用 \left[L, R\right] 区间中的整数进行编号为一次操作 \operatorname{F}\left(N, L, R\right)。这个操作的结果合法，当且仅当所有边两端端点的编号之和不超过 L+R。为了方便，我们称这个编号之和为这个边的“值”，并记点 V 的编号为 id_V。接下来我们证明这个操作的结果合法。

对于 N=1 和 N=2 的情况，这种操作的结果必然合法。

假设 N=k 和 N=k-1 时，\operatorname{F}\left(k, L, R\right) 的结果合法，不妨再令 N=k+1。在此时进行操作 \operatorname{F}\left(k+1, L, R\right)

我们设要编号为 R 的点为 P，它的父节点为 Q。不妨考虑将 P, Q 两点去掉，此时原图会分裂成若干个子树（对于上图，三个子树为 C, D 和 ABE）。将这三个子树以任意方式连接，则是一个包含 k-1 节点的树。

如图，我们把 P, Q 去掉，并分别编上号码 R 和 L，然后添上两条新的边（AC, AD），这样就是一棵树。对这棵树执行操作 \operatorname{F}\left(k-1, L+1, R-1\right) 即可。那么，剩余的几条边和蓝边都能够保证它们的值不超过 L+R。

接下来，考虑这个过程中去掉的边（QP, QC, QD），对于 QP，它的值为 L+R，是合法的。对于 Q 和它的一个子节点 S 的连线，必然有 L+1 \le id_S \le R-1，这个边的值 v = L + id_S \le L+R-1，也是合法的。故此次操作的结果是合法的。

特别地，考虑 Q 已经有编码的情况。事实上，这种情况更加简单，对于去掉点 P 的子树，我们可以执行操作 \operatorname{F}\left(k, L, R-1\right)，那么所有边的值都能保证 v \le L+R-1，而新连的边值为 L+R，依旧合法。

故由数学归纳法，原命题成立。操作 \operatorname{F}\left(N, 1, N\right) 的结果即为本题答案。

代码

这里不多加阐述，可以参考下方的代码和注释。

/**
 * @link https://www.luogu.com.cn/problem/P11206
 */

#include <bits/stdc++.h>
#define upto(i,n) for(int i=1;i<=(n);i++)

int T;
namespace Solution {
    int N;
    const int _N = 1e5+5;

    int depth[_N];  // 到根节点（1）的距离

    std::vector<int> conn[_N];  // i 和 conn[i][j] 互相连接
    int parent[_N];  // 记录父亲节点
    int filling_queue_arr[_N];
    int filled[_N];
    std::queue<int> filling_queue;

    void init() {
        // 重设，防止多测数据互相污染
        std::memset(depth, 0, sizeof(depth));
        upto(i, _N)  conn[i].clear();
        std::memset(parent, 0, sizeof(parent));
        std::memset(filling_queue_arr, 0, sizeof(filling_queue_arr));
        std::memset(filled, 0, sizeof(filled));
        scanf("%d", &N);
        int x=0, y=0;
        upto(_, N-1) {
            scanf("%d%d", &x, &y);
            conn[x].push_back(y);
            conn[y].push_back(x);
        }
    }

    void dfs_depth(int p, int prev) {  // 计算深度
        parent[p] = prev;
        depth[p] = depth[prev] + 1;

        for (auto &dest: conn[p]) {
            if (dest == prev)  continue;
            dfs_depth(dest, p);
        }
    }

    bool check() {
        upto(i, N) {
            for (auto &dest: conn[i]) {
                if (filled[i] + filled[dest] > N+1) {
                    return false;
                }
            }
        }
        return true;
    }

    void solve() {
        init();
        dfs_depth(1, 0);  // 以 1 为根节点
        // 按照深度排序填充顺序
        upto(i, N)  filling_queue_arr[i] = i;
        std::sort(filling_queue_arr+1, filling_queue_arr+1+N, [](auto a, auto b) {
            return depth[a] > depth[b];
        });
        upto(i, N)  filling_queue.push(filling_queue_arr[i]);  // 压入队列

        int L=1, R=N;  // 区间最小值和最大值
        // 依次填充
        while (not filling_queue.empty()) {
            auto cur = filling_queue.front();  filling_queue.pop();
            if (filled[cur])  continue;  // 填过的就忽略
            // 尝试在该点填充一个最大的数
            filled[cur] = R; R--;
            // 在父节点填充一个最小的数
            if (parent[cur] != 0 /* 特判，根节点不做处理 */ && not filled[ parent[cur] ]) {
                filled[ parent[cur] ] = L; L++;
            }
        }

        // 全部填充完毕
        upto(i, N)  printf("%d ", filled[i]);
        assert(check());  // 结果正确
        printf("\n");
    }
}

int main() {
    scanf("%d", &T);
    while (T --> 0)
        Solution::solve();
    return 0;
}

这里的 check() 函数事实上是无用的，不过可以方便调试。

此外，还是要提醒一下，对于多测的题目，要注意完全清空所有可能用到的数组和容器。