[R47D]树与直径

题意

给定节点数 $n$ 和直径长度 $x$（直径指任意两点简单路径边数的最大值），构造一棵满足条件的 $n$ 个节点的树，使其度数序列 $d_1,d_2,\dots,d_n$ 字典序最小。$3 \le n \le 10^5$，$2 \le x < n$。

思路

直径为 $x$ 的树必然存在一条由 $x+1$ 个节点、$x$ 条边组成的 直径链。其余 $n-x-1$ 个节点要么作为叶子直接挂到链上某个位置，要么挂到其他非链节点上形成子树。

关键观察：最大化度数为 1 的节点数

要让度数序列字典序最小，前缀应该尽可能多地填 1。因此我们要让度数为 1 的节点尽量多。

• 直径链的两个端点度数至少为 1。
• 链上中间的 $x-1$ 个位置，每个在链中已占用 2 条边，度数至少为 2，不可能 为 1。
• 剩余 $n-x-1$ 个非链节点，只要全部作为叶子挂到链的中间位置上，它们度数均为 1。

所以度数为 1 的节点数最多为 $2+(n-x-1)=n-x+1$ 个，无法更多。这 $n-x+1$ 个 1 自然放在序列最前面（分配给节点 $1,2,\dots,n-x+1$）。

中间链位置如何分配度数

设链上中间位置（共 $x-1$ 个，位于节点编号 $n-x+2,\dots,n$）的度数为 $2+c_p$，其中 $c_p$ 为挂在该位置上的叶子数，满足 $\sum c_p = n-x-1$、$c_p \ge 0$。

要让序列 $d_{n-x+2},\dots,d_n$ 字典序最小，应让靠前的位置度数尽量小，即尽量多为 2。贪心地：

• 前 $x-2$ 个中间位置不挂任何叶子，度数均为 2。
• 把全部 $n-x-1$ 个叶子集中挂到最后一个中间位置（节点 $n$），使其度数为 $2+(n-x-1)=n-x+1$。

任何把叶子分散到更前位置的方案都会让更靠前的度数变大，字典序更劣，故该方案最优。

直径合法性的验证

把叶子挂到链的最后一个中间位置（即与端点 2 相邻的那个位置）后：

• 叶子到端点 1 的距离为 $x$（叶子 $\to$ 该位置走 1 步，该位置沿链到端点 1 走 $x-1$ 步）。
• 叶子到端点 2 的距离为 $2$。
• 端点 1 到端点 2 距离为 $x$。

最大值为 $x$，直径恰好为 $x$，合法。当 $x=2$ 时中间位置只有一个，整棵树退化为星形（中心度数 $n-1$），同样合法。

答案

样例 1（$n=4,x=2$）：$n-x+1=3$ 个 1，无度数为 2 的中间位置，最后一个为 $n-x+1=3$，输出 1 1 1 3。

样例 2（$n=5,x=4$）：$n-x+1=2$ 个 1，$x-2=2$ 个 2，最后一个为 $n-x+1=2$，输出 1 1 2 2 2。

代码

import std.convert.*
import std.env.*

main(): Int64 {
    let reader = getStdIn()
    let parts = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let n = parts[0]
    let x = parts[1]
    // 字典序最小的度数序列：
    // 前 n-x+1 个节点度数为 1（直径链两个端点 + 所有 n-x-1 个额外叶子）；
    // 中间链上 x-1 个节点中，前 x-2 个度数为 2，最后一个（节点 n）吸收全部额外叶子，
    // 度数为 2 + (n-x-1) = n-x+1。
    let ones = n - x + 1   // 度数为 1 的节点个数
    let sb = StringBuilder()
    var i = Int64(0)
    while (i < ones) {
        if (i > Int64(0)) {
            sb.append(" ")
        }
        sb.append("1")
        i++
    }
    // 中间度数为 2 的节点：共 (x-1)-1 = x-2 个
    var j = Int64(0)
    let twos = x - 2
    while (j < twos) {
        sb.append(" 2")
        j++
    }
    // 最后一个节点（节点 n）吸收全部额外叶子
    let last = n - x + 1
    sb.append(" ")
    sb.append(last.toString())
    println(sb.toString())
    return 0
}