题解：P10678 『STA - R6』月

· · 题解

不 简易结论题。

首先明确一下树的直径的定义（也许就我这种蒟蒻赛前都不知道树的直径是啥）：树中距离最远的两个点之间的距离被称为树的直径。

那么根据定义我们直接想到一个结论：每次从父节点到子节点连边时我们尽量找度数更多的节点当儿子，先把度数多的节点解决了。

这个其实很容易想明白。先把需要连的边多的节点连掉，后面整棵树连边才会更均匀，才能尽量拉近最远两点间的距离。

依据这个策略我们开始构造，这里我们用变量 now 动态维护当前连到第几个点：先对所有点按度数排序，然后遍历节点，从 now 号点开始，往下不断找，找到一个能连的边就直接与当前节点连边并将其两个节点的度数减 1，并将 now 加 1，直到当前节点度数为 0。因为第一个点只能先往二号点连边，所以 now 初始为 2。

容易发现连边复杂度为 O(n)，排序复杂度为 O(n\log{n})，复杂度稳过。

附上代码：

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mk make_pair
#define mod 100000000
using namespace std;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)putchar('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
il int max(int x,int y){return x>=y?x:y;}
il int min(int x,int y){return x<=y?x:y;}
const int JYAAKIOI=1145141919810;
struct node{
    int id,x;
}a[200086],b[200086];
int T,n,now;
vector<int>l,r;
il bool cmp(node x,node y){
    return x.x>y.x;
}
signed main(){
    //freopen("jytwcsnm.in","r",stdin);
    //freopen("jytwcsnm.out","w",stdout);
    T=rd();
    while(T--){
        l.clear();r.clear();
        n=rd();
        for(int i=1;i<=n;++i)a[i].x=rd(),a[i].id=i;
        sort(a+1,a+1+n,cmp);
        now=2;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=a[i].x;++j){
                l.push_back(a[i].id);
                r.push_back(a[now].id);
                --a[now].x;
                ++now;
            }
        }
        for(int i=0;i<l.size();++i){
            wr(l[i]),putchar(' '),wr(r[i]),putchar('\n');
        }
    }
    return 0;
}