Solution
看了别的大佬的题解，感觉都是数学证明然后用树和图做的，看不懂啊。。。萌新瑟瑟发抖
用 vector 模拟树，然后贪心摸索做出来了。注意到要求最深叶子结点和最浅叶子结点的距离最短时的情况，那么此时根节点应该是树中度数最大的点，把树尽可能的拓宽，深度换宽度。
那么同理的根节点的子树的根节点应该也是该子树中度数最深的点，那么可得出该树应该是类似一个大根堆（出度不一定为 \(2\)，因此类似），且每层的数量其实是固定的（由上一层的度数之和决定，而根节点又确定），因此仅通过一次排序，便可得到由根节点到最后一个叶子结点，每层的顺序：
如：样例第四
7
1 3 2 3 1 1 1
通过结构体将每个元素的度数和原次序绑定，得如下顺序：
（后期要改度数用出度，将除了根节点之外的度数均减一）
//表格一
4
2
1 1&&&
1 2 //原次序
1 1 //度数
&&&3
1 1 2&&&
3 1 2
2 1 1
&&&5
1 1 2 2 2&&&
3 4 5 1 2
2 2 2 1 1
&&&7
1 3 2 3 1 1 1&&&
2 4 3 1 5 6 7
3 3 2 1 1 1 1
&&&
然后再将 "&&" 中的结构体装进 vector 里面模拟树（仅是因为 vector 方便打，其实用树结构体存效果一样）：
//表格二
4
2
1 1&&&1 &&& //树中存的是节点的次序
&&&2 &&&&&&1 &&& //树中存的是节点的出度
&&&0 &&&
3
1 1 2
&&&3 &&&
&&&1 2 &&&&&&2 &&&
&&&0 0 &&&
5
1 1 2 2 2
&&&3 &&&
&&&4 5 &&&
&&&1 2 &&&&&&2 &&&
&&&1 1 &&&
&&&0 0 &&&
7
1 3 2 3 1 1 1
&&&2 &&&
&&&4 3 1 &&&
&&&5 6 7 &&&&&&3 &&&
&&&2 1 0 &&&
&&&0 0 0 &&&
“&”“&” 中的是 vector 数组中每层的情况，（除了根节点之外的节点度数减了 \(1\)，转变成出度）。而决定该层数是由上一层的所有点的出度之和（第二层根据根节点的出度）。下一层中的任何一个都可做上一层节点的孩子，不影响树的最深最浅叶子结点层数。
最后把树的情况输出来即可：
如最后一例：
&&&2 &&& //节点次序
&&&4 3 1 &&&
&&&5 6 7 &&&&&&3 &&& //3->2,3->1,3->0
&&&2 1 0 &&& //2->0,2->0,2->0
&&&0 0 0 &&& //父节点领养子节点情况
//将上面的诸如 \(2\),\(0\) 之类转成\(↑\)上面树中存的节点次序输出来即可变成：
Code
#include <bits/stdc++.h>
using namespace std;
#define to(x,y); for(int x=1;x<=y;x++)
#define fr(x,y); for(int x=0;x<y;x++)
const int N = 2e5 + 20;
int t, n, sum[N];struct nd {int ord, cry;
} p[N];
vector<nd> tr[N];bool cmp(nd a, nd b) {if (a.cry == b.cry)return a.ord < b.ord;return a.cry > b.cry;
}int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);to(i, n)scanf("%d", &p[i].cry), p[i].ord = i;sort(p + 1, p + 1 + n, cmp);to(i, n) {if (i > 1)p[i].cry--;sum[i] = sum[i - 1] + p[i].cry;}int l = 1, r = 1, num, dep = 1;tr[1].push_back({p[1].ord, p[1].cry});while (r < n) {dep++;num = sum[r] - sum[l - 1];l = r + 1, r = r + num;for (int i = l; i <= r; i++)tr[dep].push_back({p[i].ord, p[i].cry});}to(i, dep - 1) {int len = tr[i].size(), idx = 0;fr(j, len) {for (int k = 0; k < tr[i][j].cry; k++) {printf("%d %d\n", tr[i][j].ord, tr[i + 1][idx + k]);}idx += tr[i][j].cry;}}to(i, dep)vector <nd>().swap(tr[i]);}return 0;
}
附带表格可视化并附解释
#include <bits/stdc++.h>
using namespace std;
#define to(x,y); for(int x=1;x<=y;x++) //丑陋的代码化简习惯
#define fr(x,y); for(int x=0;x<y;x++)
const int N = 2e5 + 20;
int t, n, sum[N];// sum 为出度前缀和，求每层的节点数
struct nd {int ord, cry;
} p[N]; //存输入数据并做预处理用
vector<nd> tr[N];//核心 vector 树bool cmp(nd a, nd b) {if (a.cry == b.cry)return a.ord < b.ord;return a.cry > b.cry;
}//排序预处理int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);
// memset(p, 0, sizeof p); //无用的初始化to(i, n)scanf("%d", &p[i].cry), p[i].ord = i;sort(p + 1, p + 1 + n, cmp);/*表格一*/
// puts("\n&&&");
// to(i, n)printf("%d ", p[i].ord);
// puts("");
// to(i, n)printf("%d ", p[i].cry);
// puts("\n&&&\n");to(i, n) {if (i > 1)p[i].cry--;//改度数为出度sum[i] = sum[i - 1] + p[i].cry;//前缀和}int l = 1, r = 1, num, dep = 1;tr[1].push_back({p[1].ord, p[1].cry});//存下根节点while (r < n) {dep++;//由上一层来到下一层num = sum[r] - sum[l - 1];//上层度数之和l = r + 1, r = r + num;for (int i = l; i <= r; i++)//“领养”子节点tr[dep].push_back({p[i].ord, p[i].cry});//存下该层子节点}/*表格二*/
// to(i, dep) {
// printf("&&&");
// int len = tr[i].size();
// fr(j, len)printf("%d ", tr[i][j].ord);
// puts("&&&");
// }
// puts("");
// to(i, dep) {
// printf("&&&");
// int len = tr[i].size();
// fr(j, len)printf("%d ", tr[i][j].cry);
// puts("&&&");
// }to(i, dep - 1) {int len = tr[i].size(), idx = 0;// idx 为领养子节点的次序fr(j, len) {for (int k = 0; k < tr[i][j].cry; k++) {printf("%d %d\n", tr[i][j].ord, tr[i + 1][idx + k]);}//输出父子idx += tr[i][j].cry;//领下一批子节点}}to(i, dep)vector <nd>().swap(tr[i]);//清空 vector 树}//完结撒花return 0;
}
