题解 | #小红的树构造#

小红的树构造

首先考虑两种特殊情况：

• : 一棵个节点的树，能取得的最大直径是 (此时树是一条链), 因此当时，无解

• , 考虑一棵个节点的树能取得的最小直径:

  • 当时，最小直径为，此时若，无解。

  • 当时，最小直径为，此时若，把这条边连起来就行了。

  • 当时，最小直径为，除了根节点(假设根为编号为的节点)以外，所有节点都与根节点直接相连，此时若，无解。

其他都是有解的情况，构造方法如下：

• 先构造出直径：连接这些边，这样从到的距离为，可以作为树的直径。

• 添加其他节点：对于其他节点，为了不干扰直径的长度，可以直接把这些节点和这个节点相连，这样可以维持直径不变。

def solve(testcase):
    n, k = MI()

    if k == 1:
        if n == 2:
            print(1, 2)
        else:
            print(-1)
        return

    if n <= k:
        print(-1)
    else:
        A = []
        for i in range(1, k + 1):
            A.append(f"{i} {i + 1}")
        for i in range(k + 2, n + 1):
            A.append(f"2 {i}")
        print("\n".join(A))

for testcase in range(1):
    solve(testcase)