CF1714F Build a Tree and That Is It 题解

题目链接：CF1714F Build a Tree and That Is It

题意：

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

现有四个整数 $ 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}, d_{31} $ ( $ 3 \le n \le 2\times 10^5,~1 \le d_{12}, d_{23}, d_{31} \le n-1 $ ) 。

输入数据保证所有 $ n $ 不超过 $ 2\times 10^5 $ 。

输出格式：

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

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

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

因为选任意合法点作根都是一样的，所以我们可以钦定 $1$ 为根，尝试构造。

首先考虑什么情况无解：

给出的三个 $d$ ，任意两者之和必须大于等于第三者，否则无解。
用到的连接边不能超过 $n$ 条。
把三个 $d$ 记为 $a,b,c$ ，则 $a + b + c$ 是偶数。

接着考虑如何构造。不妨假设 $2$ 是离 $1$ 最近的那个点。

对于路径 $1\leadsto \mathrm{LCA}(2,3)$ ，我们从 $4$ 开始拼接，长度为 $(a + c - b) / 2$ ，画下图应该就明白了

确定好 LCA 后，就是暴力拼接 $2,3$ 了。完成后，可能还剩下一些节点没用到，我们直接把他们挂在 $1$ 上就好了

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,a,b,c,d1,d2,d3;
void link(int x,int y) { cout << x << ' ' << y << '\n'; }
void solve()
{
    cin >> n >> a >> b >> c;
    d1 = (a + c - b) / 2; d2 = (a + b - c) / 2; d3 = (b + c - a) / 2;
    if(d1 < 0 || d2 < 0 || d3 < 0 || d1 + d2 + d3 >= n || ((a + b + c) & 1))
        return cout << "NO" << '\n', void(0);
    cout << "YES" << '\n'; int x = 2, y = 3; if(a > c) { swap(a,c); swap(x,y); }
    int lst = 1, now = 4, cnt = 0;
    if(a + b == c)
    {
        for(int i = 1; i < a; i++) { link(lst, now); lst = now++; }
        link(lst, x); lst = x;
        for(int i = 1; i < b; i++) { link(lst, now); lst = now++; }
        link(lst, y);
    }else
    {
        for(int i = 1; i <= (a + c - b) / 2; i++,cnt++) { link(lst, now); lst = now++; }
        a -= cnt; c -= cnt; int tmp = lst;
        for(int i = 1; i < a; i++) { link(lst, now); lst = now++; }
        link(lst, x); lst = tmp;
        for(int i = 1; i < b - a; i++) { link(lst, now); lst = now++; }
        link(lst, y);
    }
    for(int i = now; i <= n; i++) link(1, i);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}