CFR 658 C. Bear and Forgotten Tree 3 ( Adhoc Tree )
Problem - C - Codeforces
細かいケースが多く、割と面倒くさい。
でもちゃんと考えてたら、実は簡単。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, d, h; void solve(){ if( n < h + 1 ) return (void)puts("-1"); // 一直線でやっても足りない if( !( h <= d && d <= 2 * h ) ) return (void)puts("-1"); // 直径は木の高さとその二倍の中にある if( d == h && h == 1 && n != 2 ) return (void)puts("-1"); // 特別 for( int i = 2; i <= h + 1; ++i ) printf("%d %d\n", i - 1, i); for( int i = h + 2; i <= n && i <= d + 1; ++i ) printf("%d %d\n", i == h + 2 ? 1 : i - 1, i); for( int i = d + 2; i <= n; ++i ) // 深さが 1でない限り、適当な葉の兄弟にして余ったnodeを処理する printf("%d %d\n", h, i); } int main(){ scanf("%d%d%d", &n, &d, &h); solve(); return 0; }