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;
}