cf1003 E. Tree Constructing

题意：

构造一棵树，要求节点数为 \(n\)，直径为 \(d\)，每个点的度不超过 \(k\)

思路：

先构造一条 \(d+1\) 个节点、\(d\) 条边的链。然后在链上加分支。

记链上节点的编号为 \(1,2,\cdots , d+1\)。以链上某点 \(i\) 为根构造树，树中节点的深度不能超过 \(\min \{i-1,d+1-i \}\)。当然度数也有要求。dfs 构造即可

const signed N = 5 + 4e5;
int n, dis, deg;
int idx, p[N];

void dfs(int u, int dep_u, int dep_lim, int deg_lim) {
    if(!deg_lim || dep_u == dep_lim) return;
    while(deg_lim--) {
        if(idx == n) break;
        p[++idx] = u, dfs(idx, dep_u+1, dep_lim, deg-1);
    }
}

void sol() {
    cin >> n >> dis >> deg;

    if(n > 2 && deg <= 1) return cout << "NO", void(); //特判

    for(int i = 1; i <= dis; i++) p[i+1] = i; //先构造一条链作为直径
    idx = dis + 1;

    for(int i = 2; i <= dis+1 && idx < n; i++) //dfs构造
        dfs(i, 0, min(i-1, dis+1-i), deg-2);

    if(idx != n) cout << "NO";
    else {
        cout << "YES\n";
        for(int i = 2; i <= n; i++) cout << p[i] << ' ' << i << endl;
    }
}