CF1003E - Tree Constructing

题目传送门

知识点：贪心

题意

给定 \(n\) 个顶点，问是否能够构造出一棵直径为 \(d\) 的树，且每个顶点的度数最多为 \(k\) 。

思路

我们要构造出一棵树，使得其直径长度一定为 \(d\) ，那么我们可以先选择 \(d + 1\) 个点，让这些点构成一条树链即可。

接着，考虑其他点如何摆放的问题。我们基于上面的树链来放置点，那么我们可以先维护每个点距离这条树链两端的最远距离，如果最远距离会超过 \(d\) ，那么说明往这里放点会导致直径过大，因此不可以放置。

然后我们就可以直接按照度数限制，然后直接放置了。

实现

#include <bits/stdc++.h>

auto main() -> int {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, d, k;
    std::cin >> n >> d >> k;

    if (n <= d || (n > 2 && k == 1)) {
        std::cout << "NO\n";
        return 0;
    }

    std::vector adj(n, std::vector<int>{});
    std::vector<int> deg(n);
    std::vector<std::pair<int,int>> edge;
    std::vector<int> max_len(n);

    edge.reserve(n + 1);

    auto add_edge = [&](int u, int v) -> void {
        deg[u] += 1;
        deg[v] += 1;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        edge.emplace_back(u, v);
    };

    for (int i = 0; i < d + 1; i ++) {
        max_len[i] = std::max(i, d - i);
    }
    for (int i = 0; i + 1 < d + 1; i ++) {
        add_edge(i, i + 1);
    }

    int tag = d + 1;
    std::vector<bool> vis(n);
    auto dfs = [&](auto &self, int from, int come) -> void {
        if (vis[from]) {
            return;
        }
        vis[from] = true;
        if (tag >= n) {
            return;
        }
        if (max_len[from] + 1 <= d) {
            while (deg[from] < k && tag < n) {
                add_edge(from, tag);
                max_len[tag] = max_len[from] + 1;
                tag += 1;
            }
        }
        for (auto to : adj[from]) {
            if (to != come)
                self(self, to, from);            
        }
    };

    for (int i = 1; i <= d && tag < n; i ++) {
        dfs(dfs, i, -1);
    }

    if (std::ranges::max(deg) > k || std::ranges::min(deg) == 0 || (int)edge.size() != n - 1) {
        std::cout << "NO\n";
    } else {
        std::cout << "YES\n";
        for (auto [u, v] : edge) {
            std::cout << u + 1 << ' ' << v + 1 << '\n';
        }
    }
}