526互联

[ARC117D] Miracle Tree 题解

发布时间 2023-08-17 15:46:40作者: User-Unauthorized

题意

给定一棵 \(n\) 个节点的树，要求构造出一个点权序列 \(E\)，满足以下三个条件：

1.所有 \(E_i\ge 1(1\le i\le n)\)。

2.对于任意一组 \((i,j)(1 ≤ i < j ≤ N)\)，使 \(|E_i-E_j|\ge dist(i,j)\)，\(dist\) 即树上两点距离。

3.使 \(E\) 中的最大值最小。

题解

首先考虑前两个条件，设存在长度为 \(n\) 排列 \(p\)，使得 \(\forall i \in \left[1, n\right) E_{p_i} < E_{p_{i + 1}} \land E_{p_{i + 1}} - E_{p_i} \le dist\left(p_i, p_{i + 1}\right)\)。因为对于树上任意三点 \(i, j, k\)，都有

\[dist(i, j) \le dist(i, k) + dist(j, k) \]

所以对于任意 \(1 \le i < k < j \le n\)，有

\[dist(p_i, p_j) \le dist(p_i, p_k) + dist(p_j, p_k) \le E_{p_k} - E_{p_i} + E{p_j} - E_{p_k} = E_{p_j} - E_{p_i} \]

因此可以得到一个满足前两个要求的构造方法，对于任意 \(1 \le i < n\)，构造 \(E_{p_i},E_{p_{i + 1}}\) 使得 \(E_{p_{i + 1}} - E_{p_i} = dist(p_i, p_{i + 1})\)。

接下来考虑第三个要求，对于排列 \(p\)，序列 \(E_i\) 的最大值为

\[\sum\limits_{i = 1}^{n - 1} \left(E_{p_{i + 1}} - E_{p_i}\right) + 1= \sum\limits_{i = 1}^{n - 1} dist(p_{i + 1}, p_i) + 1 \]

考虑到 \(\sum\limits_{i = 1}^{n - 1} dist(p_{i + 1}, p_i) + dist(p_1, p_n) + 1\) 的最小值为 \(2\left(n - 1\right) + 1\)，即欧拉回路的长度，此时每个边都被经历两次，考虑在此基础上最大化 \(dist(p_1, p_n)\)，显然满足 \(dist(x, y)\) 最大的 \(x, y\) 为树的直径的两个端点。

这样我们就得到了最终的构造方法：求出树的直径，然后从直径的一个端点进行欧拉环游，其中对于每个经过的节点，如果存在一条边在树的直径上，那么最后经过这条边。这样在到达直径的另一个端点时，可以保证所有节点均已访问过，故可以直接结束递归。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;

valueType N;
ValueMatrix G;
ValueVector depth;

valueType dfs(valueType x, valueType from) {
    valueType maxDepth = x;

    depth[x] = depth[from] + 1;

    for (auto const &iter: G[x]) {
        if (iter == from)
            continue;

        valueType const result = dfs(iter, x);

        if (depth[result] > depth[maxDepth])
            maxDepth = result;
    }

    return maxDepth;
}

bitset tag;

bool addTag(valueType x, valueType from, const valueType &target) {
    if (x == target)
        return tag[x] = true;

    for (auto const &iter: G[x]) {
        if (iter == from)
            continue;

        if (addTag(iter, x, target))
            tag[x] = true;
    }

    return tag[x];
}

ValueVector ans;
valueType dfsCount = 0;

void calc(valueType x, valueType from) {
    ans[x] = ++dfsCount;

    valueType end = -1;

    for (auto const &iter: G[x]) {
        if (iter == from)
            continue;

        if (tag[iter]) {
            end = iter;

            continue;
        }

        calc(iter, x);

        ++dfsCount;
    }

    if (end != -1) {
        calc(end, x);

        ++dfsCount;
    }
}

int main() {
    std::cin >> N;

    G.resize(N + 1);
    depth.resize(N + 1, 0);

    for (valueType i = 1; i < N; ++i) {
        valueType a, b;

        std::cin >> a >> b;

        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    std::fill(depth.begin(), depth.end(), 0);
    valueType const A = dfs(1, 0);
    std::fill(depth.begin(), depth.end(), 0);
    valueType const B = dfs(A, 0);

    tag.resize(N + 1, false);

    addTag(A, 0, B);

    ans.resize(N + 1, 0);

    calc(A, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cout << ans[i] << " ";

    std::cout << std::endl;

    return 0;
}