题解：CF639B Bear and Forgotten Tree 3

Focux_ · 2026-01-12 20:05:47 · 题解

分讨构造题。

首先肯定判掉无解。无解情况有 h\times 2<d，即根节点伸出的两条最长链拼起来小于直径的情况，还有一个特殊的 d=1 的情况，此时树上最多有两个节点，否则剩下的点不管挂在哪都会违规。

接着就是考虑构造方式了。

首先我们肯定需要一条从根节点出发长度为 h 的链，输出这条链后需要用这条链和从根节点出发的另一条链拼成一条长为 d 的链。

剩下的点我们需要找一个节点挂上去。容易想到若 h \ne d，则挂到 1 节点上不会改变最长链，对答案无影响。而若 h=d，由于我们前面已经判掉了 d=1 的情况，所以直接挂到 2 节点上对答案无影响。

显然 \mathcal{O}(n)。

照着以上思路做一遍即可，没什么细节。

#include<bits/stdc++.h>
using namespace std;
long long n,h,d;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>d>>h;
    if(h*2<d)
    {
        cout<<-1;
        return 0;
    }
    if(d==1)
    {
        if(n==2)
            cout<<"1 2";
        else
            cout<<-1;
        return 0;
    }
    for(int i=2;i<=h+1;i++)
        cout<<i-1<<' '<<i<<'\n';
    if(h!=d)
    {
        cout<<"1 "<<h+2<<'\n';
        for(int i=h+3;i<=d+1;i++)
            cout<<i-1<<' '<<i<<'\n';
        for(int i=d+2;i<=n;i++)
            cout<<"1 "<<i<<'\n';
    }
    else
    {
        for(int i=h+2;i<=n;i++)
            cout<<"2 "<<i<<'\n';
    }
    return 0;
}