题解：CF639B Bear and Forgotten Tree 3

Rex01 · 2025-04-07 14:26:05 · 题解

CF639B 题目传送门

题目大意

请你构造一棵包含 n 个节点，其中节点编号从 1 到 n，并以 1 号节点为根节点，直径为 d，高度 h 的树。其中树的直径为树上两节点之间的最大距离，树的高度指的是根节点到其它节点的最大距离。若满足，则按任意顺序输出每一条边，否则输出 -1。

解决方法

首先考虑特殊情况：

• 特判一：当 n=2 时，只有 h=1 且 d=1 可以。
• 特判二：当 2 \times h < d 时，因为无解，所以输出 −1。

其他情况正常考虑：构造一棵 n 个点，深度 h，最长链长度为 d 的树。先从根构造两条长度分别为 d-h 和 h 的链，然后剩下的点如果 d\not=h 就挂在根上，输出 1 即可，如果 d=h 就随便挂在除根和叶子以外的位置上，输出 2 即可。

代码展示

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, d, h;//建议scanf,更快
    scanf("%d%d%d", &n, &d, &h);
    if(d > (2 * h) || (d == h && h == 1 && n > 2))
    //1.通过样例可知d必须<=2h若不满足就输出-1
    //2.当d=h=1且n>2时，也输出-1
    {
        printf("-1\n");//建议printf,更快
        return 0;
    }
    for(int i = 2; i <= h + 1; i++)
        printf("%d %d\n", i-1, i);
    for(int i = h + 2; i <= d + 1; i++)
  //分类讨论
        if(i == h + 2) printf("1 %d\n", i);
        else printf("%d %d\n", i-1, i);
    for(int i = d + 2; i <= n; i++)
        if(d != h) printf("1 %d\n", i);
        else printf("2 %d\n", i);
    return 0;
}