題目鏈接：D - Flower-like Pseudotree

題目大意：給定度數(shù)數(shù)組 \({d_n}\)，要求構(gòu)造一個(gè) \(n\) 個(gè)點(diǎn) \(n\) 條邊的連通圖（也就是基環(huán)樹），允許有重邊，但不能有自環(huán)。需要滿足第 \(i\) 個(gè)點(diǎn)的度數(shù)恰好為 \(d_i\)，并且將環(huán)上的邊全部刪去后，剩下的每棵樹的高度（以原先在環(huán)上的點(diǎn)為根）相同。

首先考慮幾個(gè)特殊情況：

• 當(dāng) \(\sum d_i\neq 2n\) 時(shí)，無(wú)解
• 若 \(\forall i,d_i=2\)，則直接輸出一個(gè)大小為 \(n\) 的環(huán)

將構(gòu)造分兩步完成，先將非葉子結(jié)點(diǎn)全部安排好以完成深度限制，然后再把所有葉子結(jié)點(diǎn)連到這些點(diǎn)上以符合度數(shù)限制，其中后者做法平凡。基于這一點(diǎn)考慮，如果不存在度數(shù)為 \(2\) 的點(diǎn)，那么直接把所有非葉子結(jié)點(diǎn)連成一個(gè)環(huán)就能完成第一步構(gòu)造。剩下的情況都是必然存在一個(gè)度數(shù)為 \(2\) 的點(diǎn)的。

接下來(lái)，考慮在環(huán)上延伸出點(diǎn)以完成構(gòu)造。這時(shí)發(fā)現(xiàn)由于在環(huán)上的點(diǎn)度數(shù)必須 \(\gt 2\)，而環(huán)的大小至少為 \(2\)。所以若度數(shù) \(>2\) 的點(diǎn)數(shù)為 \(1\) 則無(wú)解。顯然，若不在環(huán)上的非葉子結(jié)點(diǎn)個(gè)數(shù)是環(huán)大小的倍數(shù)，那么直接在環(huán)上掛幾條長(zhǎng)度相等的鏈即可。于是對(duì)環(huán)長(zhǎng)為 \(2\) 的情況進(jìn)行討論。

若欽定了環(huán)長(zhǎng)為 \(2\)，那么只需要判斷剩余的非葉子結(jié)點(diǎn)個(gè)數(shù)是否為偶數(shù)，若是則直接可以完成構(gòu)造。若不是，那我們先盡量讓兩邊的鏈長(zhǎng)平均，這樣有一邊會(huì)多出來(lái)一個(gè)點(diǎn) \(x\) ，考慮將這個(gè)多出來(lái)的點(diǎn)移到某個(gè)深度比 \(x\) 小的點(diǎn) \(y\) 后面，讓他作為 \(y\) 的兒子。

此時(shí)，\(dep(x)=dep(y)+1\)，于是只需保證在刪去\(x\) 后，\(y\) 不是當(dāng)前基環(huán)樹上的葉子結(jié)點(diǎn)即可。那么可以在一開始放鏈的時(shí)候，優(yōu)先讓 \(d_i\) 大的點(diǎn)先連（深度更小），這樣 \(x\) 在找爹的時(shí)候，直接找深度最淺的有空位的父親即可，這樣做一定是較優(yōu)的。

接下來(lái)說(shuō)明用上述方法無(wú)法完成構(gòu)造時(shí)，一定無(wú)解，不感興趣可跳過(guò)。

先考慮無(wú)法構(gòu)造時(shí)，是什么樣的一種情況。

此時(shí)一定是 \(x\) 在找爹時(shí)，找不到一個(gè)比當(dāng)前爹深度更淺的，且有空位的新爹了。

由于我們是優(yōu)先連 \(d_i\) 更大的點(diǎn)，所以此時(shí)所有的點(diǎn)一定都沒(méi)有空位，那么顯然除了和當(dāng)前 \(x\) 的父親深度一樣的兩個(gè)點(diǎn)，其它點(diǎn)的 \(d_i\) 一定為 \(2\)，而環(huán)上的兩個(gè)點(diǎn) \(d_i=3\)。

當(dāng) \(x\) 的父親深度 \(\gt 1\)（環(huán)上的點(diǎn)深度看做 \(0\)）時(shí)，深度為 \(1\) 的點(diǎn)沒(méi)有空位，那么其 \(d_i\) 一定為 \(2\)。對(duì)應(yīng)非葉子結(jié)點(diǎn)的 \(d_i\) 可重集的情況就是 \(\{3,3,2,2,2,\dots,2,2\}\)，其中 \(2\) 的個(gè)數(shù)為奇數(shù)。那么顯然此時(shí)只能有兩個(gè)點(diǎn)在環(huán)上，因?yàn)橛腥~子時(shí)度數(shù)為 \(2\) 的點(diǎn)不能在環(huán)上。于是無(wú)法通過(guò)調(diào)整環(huán)長(zhǎng)來(lái)求解，對(duì)應(yīng)情況無(wú)解。

當(dāng) \(x\) 的父親深度為 \(1\) 時(shí)，此時(shí)是深度為 \(0\) 的點(diǎn)沒(méi)有空位，對(duì)應(yīng)情況則為 \(\{3,3,2\ or\ 3,2\ or\ 3,2\}\)。此時(shí)雖然可以調(diào)整環(huán)長(zhǎng)，但是調(diào)整環(huán)長(zhǎng)后剩下的非葉子結(jié)點(diǎn)不足以連出一條長(zhǎng)度為 \(1\) 的鏈，所以也無(wú)解。

當(dāng) \(x\) 的父親深度為 \(0\) 時(shí)，那么此時(shí)情況為 \(\{G_1,G_2,2\}\)，\(G_i\) 表示某個(gè) \(\gt 2\) 的數(shù)，與 \(x\) 的父親深度 \(\gt 1\) 的情況一樣，也是無(wú)解的。

那么完成幾個(gè)特殊情況的判斷后，貪心連鏈即可。由于需要找新爹的點(diǎn)最多只會(huì)有一個(gè)，所以直接按度數(shù)從大到小找到一個(gè)滿足條件的點(diǎn)就好。

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define GG {printf("No\n");return;}
int T,n,fa[N],dep[N];
struct rua
{
	int deg,id;
	void read(int i){scanf("%d",&deg),id=i;}
	bool operator <(const rua &t)const{return deg>t.deg;}
}a[N];
void init()
{	
	int d2=0,d1=0;
	long long sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		dep[i]=fa[i]=0;
		a[i].read(i);
		if(a[i].deg==1)d1++;
		if(a[i].deg==2)d2++;
		sum+=a[i].deg;
	}
	if(sum!=2*n)GG
	if(n-d1-d2==1)GG
	if(d2==n){
		printf("Yes\n");
		for(int i=1;i<=n;i++)
			printf("%d %d\n",i,i%n+1);
		return;
	}
	sort(a+1,a+n+1);
	if(d2==0){
		printf("Yes\n");
		vector<int>d;
		int id=1;
		while(id<=n && a[id].deg>1)id++;id--;
		for(int i=1;i<=id;i++){
			printf("%d %d\n",a[i].id,a[i%id+1].id);
			for(int j=1;j<=a[i].deg-2;j++)d.push_back(a[i].id);
		}
		for(int i=id+1;i<=n;i++)
			printf("%d %d\n",a[i].id,d[i-id-1]);
		return;
	}
	int lst=0;
	a[1].deg-=2,a[2].deg-=2;
	for(int i=3;a[i].deg>=2;i++){
		a[i].deg--;
		fa[a[i].id]=a[i-2].id;
		dep[a[i].id]=dep[fa[a[i].id]]+1;
		a[i-2].deg--;
		lst=i;
	}
	if(lst&1){
		int f=0;
		for(int i=1;i<lst;i++)
			if(a[i].deg && dep[a[i].id]<dep[fa[a[lst].id]]){
				f=1;
				a[lst-2].deg++;
				fa[a[lst].id]=a[i].id;
				a[i].deg--;
				break;
			}
		if(f==0)GG
	}
	vector<int>d;
	for(int i=1;i<=lst;i++)
		for(int j=1;j<=a[i].deg;j++)
			d.push_back(a[i].id);
	for(int i=lst+1;i<=n;i++)
		fa[a[i].id]=d[i-lst-1];
	printf("Yes\n");
	for(int i=1;i<=2;i++)
		printf("%d %d\n",a[i].id,a[i%2+1].id);
	for(int i=3;i<=n;i++)
		printf("%d %d\n",a[i].id,fa[a[i].id]);
}
int main()
{
	scanf("%d",&T);
	while(T--)init();
}