思路
由于题目中说这是一棵无根树，不太方便思考，于是，我们可以假装把这棵树看做有根树。
首先我们令 \(d_1,d_2,d_3\) 分别表示从根节点到节点 \(1,2,3\) 的长度（不算相交部分）。
那么我们可以得到下式：
\[ \left\{\begin{matrix} d_{12} = d_1 + d_2\\ d_{13} = d_1 + d_3\\ d_{23} = d_2 + d_3\\ \end{matrix}\right. \]我们已知 \(d_{12},d_{13},d_{23}\)，那么我们尽可能的将 \(d_1,d_2,d_3\) 用 \(d_{12},d_{13},d_{23}\) 表示。
然后，根据将三式互相代入得：
\[ \left\{\begin{matrix} d_1 = \frac{d_{12} + d_{13} - d_{23}}{2}\\ d_2 = \frac{d_{12} + d_{23} - d_{13}}{2}\\ d_3 = \frac{d_{13} + d_{23} - d_{12}}{2}\\ \end{matrix}\right. \]知道了上述式子，我们可以先来看一下输出 NO 的情况。
- \(d_{1} < 0 \operatorname{or} d_2 < 0 \operatorname{or} d_3 < 0\)，一定无解。因为如果距离为负了一定不成立。
- \(d_1 + d_2 + d_3 \geq N\)，一定无解。因为如果最短的距离之和（可以理解为最少需花费的节点数量减 \(1\)）大于了上限，一定无解。
- \((d_{12} + d_{13} + d_{23}) \bmod 2 = 1\)，一定无解。因为我们的 \(d_1,d_2,d_3\) 一定是整数，如果它们三数相加不是 \(2\) 的倍数，那么最后的 \(d_1,d_2,d_3\) 一定不为整数。
后面我们直接挨着挨着加点即可。
需要注意的是，有可能建立完 \(d_1 + d_2 + d_3\) 个节点后，没有花完 \(N\) 个点，我们只需将剩下的点随便加到某一个节点之下即可。
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
int T,n,a,b,c,d;
int arr[15];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
int main(){
T = read();
while (T--){
n = read();
a = read();
b = read();
c = read();
arr[1] = a + c - b >> 1;
arr[2] = a + b - c >> 1;
arr[3] = b + c - a >> 1;
if (arr[1] < 0 || arr[2] < 0 || arr[3] < 0 || arr[1] + arr[2] + arr[3] >= n || a + b + c & 1) puts("NO");//判断无解
else{
puts("YES");
int idx = 3,r = 0;
for (re int i = 1;i <= 3;i++){//找出一个根
if (!arr[i]){
r = i;
break;
}
}
if (!r) r = idx = 4;//如果没找到直接随便认一个
for (re int i = 1;i <= 3;i++){
if (i == r) continue;
printf("%d ",r);//挨个加边
for (re int j = 1;j < arr[i];j++) printf("%d\n%d ",++idx,idx);
printf("%d\n",i);
}
while (idx < n) printf("1 %d\n",++idx);//加剩下的点
}
}
return 0;
}