题解：CF639B Bear and Forgotten Tree 3

· · 题解

一道简单构造题。 先构造出两条链（如图）。

            1
           / \
          2  h + 2
         /     \
        .       .
       .         .
      .           .
     /             \
    h               d
   /                 \
 h + 1              d + 1

此时还剩下一些点，

这时分类讨论，

\begin{cases} 将剩下的点挂在除根和叶子外的任意节点 & d=h \\ 将剩下的点挂在根上 & d \ne h\end{cases}

然后 d>2 \times h 是无解的，d=h=1 且 n>2 的时候也无解。

code：

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

int n, d, h;

int main() {
    cin >> n >> d >> h;
    if (d > 2 * h || (d == 1 && h == 1 && n > 2)) { // 特判
        cout << "-1\n";
        return 0;
    }
    for (int i = 2; i <= h + 1; i ++) cout << i - 1 << " " << i << "\n";
    for (int i = h + 2; i <= d + 1; i ++) cout << (i == h + 2 ? 1 : i - 1) << " " << i << "\n";
    for (int i = d + 2; i <= n; i ++) cout << (d == h ? 2 : 1) << " " << i << "\n";
    return 0;
}