题意：给出n个点的度数列 上限（实际点可以小于该度数列）问可以构造简单路最大长度是多少（n个点要连通 不能有平行边、重边）
思路：直接构造一条长链 先把度数为1的点 和度数大于1的点分开 先把度数大于1的点连在一起 然后把度数为1的点连在两边可以涨最多2的长度（如果有大于等于2的度数为1的点）
随后就涨不了长度了，还要把度数为1的点接在链上 判断是否可以构成这样一颗树
（在while里面少写了度数-- WA了两次7 QAQ）
1 #include<bits/stdc++.h> 2 #define pb push_back 3 #define pii pair<int,int> 4 #define mkp make_pair 5 #define S second 6 #define F first 7 using namespace std; 8 const int maxn=2e5+6; 9 const int inf =0x3f3f3f3f; 10 vector<pii>v; 11 vector<int>v1; 12 int vis[maxn]; 13 pii ans[maxn]; 14 int main(){ 15 int n; 16 scanf("%d",&n); 17 int tmp; 18 for(int i=1;i<=n;i++){ 19 scanf("%d",&tmp); 20 if(tmp==1)v1.pb(i); 21 else { 22 v.pb(mkp(tmp,i)); 23 } 24 } 25 if(n==2){ 26 cout<<"YES "<<2<<endl; 27 cout<<1<<endl; 28 cout<<1<<" "<<2<<endl; 29 return 0; 30 } 31 //cout<<v.size()<<endl; 32 int cnt=0; 33 int len=0; 34 sort(v.begin(),v.end()); 35 for(int i=0;i<int(v.size())-1;i++){ 36 ans[cnt++]=mkp(v[i].S,v[i+1].S); 37 v[i].F--; 38 v[i+1].F--; 39 len++; 40 } 41 if(v1.size()>=2){ 42 int p=2; 43 len+=2; 44 if(v.size()&&v[0].F){ 45 v[0].F--; 46 ans[cnt++]=mkp(v[0].S,v1[0]); 47 } 48 49 if(v.size()&&v[int(v.size())-1>=0?v.size()-1:0].F){ 50 v[int(v.size())-1>=0?v.size()-1:0].F--; 51 ans[cnt++]=mkp(v[int(v.size())-1>=0?v.size()-1:0].S,v1[1]); 52 } 53 // ans[cnt++]=mkp(v[0].S,v1[0]); 54 55 for(int i=0;i<int(v.size());i++){ 56 while(p<v1.size()&&v[i].F>0){ 57 ans[cnt++]=mkp(v[i].S,v1[p]); 58 p++; 59 v[i].F--; 60 } 61 if(p==v1.size())break; 62 } 63 } 64 else { 65 66 if(v1.size()==1){ 67 len+=1; 68 ans[cnt++]=mkp(v1[0],v[0].S); 69 } 70 } 71 //cout<<cnt<<endl; 72 if(cnt!=n-1){ 73 cout<<"NO\n"; 74 return 0; 75 } 76 cout<<"YES ";cout<<len<<endl; 77 cout<<cnt<<endl; 78 for(int i=0;i<cnt;i++){ 79 cout<<ans[i].F<<" "<<ans[i].S<<endl; 80 } 81 return 0; 82 }