Build a Tree and That Is It

Created by LXC on Fri Mar 29 15:05:04 2024

https://codeforces.com/problemset/problem/1714/F

ranting: 1900

tag: constructive algorithms, implementation, trees

problem

树是一个没有环的无向连通图，注意，在本题中，我们讨论的是无根树

现有四个整数 $ n, d_{12}, d_{23} $ 和 $ d_{31} $ . 构建一颗满足以下条件的树:

• 包含从 $ 1 $ 到 $ n $ 的 $n$ 个节点,
• 从节点 $ 1 $ 到节点 $ 2 $ 的距离（最短路的长度）为 $ d_{12} $ ,
• 从节点 $ 2 $ 到节点 $ 3 $ 的距离为 $ d_{23} $ ,
• 从节点 $ 3 $ 到节点 $ 1 $ 的距离为 $ d_{31} $ .

输出满足条件的任意一棵树；若不存在，请证明.

输入

第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) 表示测试组数.

接下来 $ t $ 组, 每组一行数据包含 $4$ 个整数 $ n, d_{12}, d_{23} $ and $ d_{31} $ ( $ 3 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1 $ ).

输入数据保证所有 $ n $ 不超过 $ 2\cdot10^5 $ .

输出

对于每一组数据，若存在这种树，输出YES；若不存在，输出NO.

对于存在的情况，额外输出 $ n-1 $ 行来描述这棵树的边（一对正整数 $ x_i, y_i $ 表示第 $ i $ 条边连接第 $ x_i $ 号节点和第 $ y_i $ 号节点.

你可以按照任何顺序输出这些边及其顶点，若有多种解，输出其中一种即可.

solution

1,2,3三个节点都会经过一个中心

设1,2,3三个点到中心节点的距离为a,b,c

那么a+b+c = (d12+d13+d23)/2

我们可以得到三个节点到中心的距离,如果距离有负数,说明没有答案

进一步我们知道需要多少个节点,需要的节点个数超过n则有没有答案

之后便是构造无根树

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, d12, d23, d13;
    cin >> n >> d12 >> d23 >> d13;
    int s = d12+d23+d13;
    if (s%2) {
        cout <<"NO\n";
        return ;
    }
    s/=2;
    int d[4] = {0, s-d23, s-d13, s-d12};
    if (d[1]<0 || d[2]<0 || d[3]<0 || d[1]+d[2]+d[3]+1>n) {
        cout << "NO\n";
        return ;
    }
    cout << "YES\n";
    int nd = 5;
    int c = 4;
    for (int i=1; i<=3; i++) {
        if (d[i] == 0) {
            nd = 4;
            c = i;
        }
    }
    // cout << nd << " -- " << c << endl;
    for (int j=1; j<=3; j++) {
        int pre = j;
        if (c == j) continue;
        for (int i=0; i<d[j]-1; i++) {
            cout << pre << " " << nd << "\n";
            pre = nd;
            nd++;
        }
        cout << pre << " " << c << "\n";
    }
    while (nd <= n) {
        cout << "1 " << nd << "\n";
        nd++;
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}