牛客月赛55 至至子的长链剖分

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

对于 nnn 个节点有根树（点的编号从 111 到 nnn），我们设节点 uuu 的“长链长度”为 huh_uhu​，其可以通过如下方式计算：

hu={0if u is a leaf nodemax⁡v∈son⁡(u){hv}+1otherwiseh_u =

{0if u is a leaf nodemaxv∈son⁡(u){hv}+1otherwise" role="presentation">{0maxv∈son(u){hv}+1if u is a leaf nodeotherwise$$\{\begin{array}{ll}0& \text{if }u\text{ is a leaf node}\\ {\displaystyle \underset{v\in \mathrm{son}(u)}{max}\{h_v\}+1}& \text{otherwise}\end{array}$$

hu​=⎩⎨⎧​0v∈son(u)max​{hv​}+1​if u is a leaf nodeotherwise​

即对于叶子节点，其 hhh 值为 000，否则为所有儿子节点中最大的 hhh 值 +1+1+1。
 

现给定一棵树的 h1,h2,⋯ ,hnh_1,h_2,\cdots, h_nh1​,h2​,⋯,hn​，请还原该树的形态，或报告无解。如有多棵满足限制的树，输出任意一棵即可，详见输出格式。

其中，叶子节点指没有子节点的节点，son(u)\mathrm{son}(u)son(u) 表示 uuu 节点的儿子节点构成的集合。

输入描述:

本题一个测试点内包含多组数据。

第一行一个正整数 TTT，表示数据组数，1≤T≤100001\le T\le 100001≤T≤10000。

每组数据的第一行包含一个正整数 nnn，表示树的节点数，保证 1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105 且 ∑n≤3×105\sum n\le 3\times 10^5∑n≤3×105。

接下来一行 nnn 个整数 h1,h2,⋯ ,hnh_1, h_2,\cdots, h_nh1​,h2​,⋯,hn​，意义如上所述，保证 0≤hi 
 
输出描述:
 
 
对于每组数据，按照如下格式输出：

如果无解，输出一行一个整数 −1-1−1 即可。

否则先在第一行输出根节点的编号 rrr。接下来输出 n−1n-1n−1 行，每行两个正整数 u,vu,vu,v，表示你构造的树内有连边 (u,v)(u,v)(u,v)。请保证你输出的是一棵树。
 
 
示例1
 
 
输入
 
 
复制3 5 2 3 1 0 0 6 1 1 0 0 0 0 2 1 0
 
 
3
5
2 3 1 0 0 
6
1 1 0 0 0 0 
2
1 0
 
 
输出
 
 
复制2 2 1 1 3 3 5 2 4 -1 1 1 2
 
 
2
2 1
1 3
3 5
2 4
-1
1
1 2
 
 
说明
 
 
 
 
对于第一组数据，有下面几种（未列出全部）合法的方案：
 
 
 
 
 
 
第二组数据无解，故输出 −1-1−1。

 第三组数据只有一组解，树根为 111 且只有一条边 (1,2)(1,2)(1,2)。
 

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
#define endl '\n'
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
ll n, m, t, a, b, c, d, i, j, N = 1e5 + 2;
vector<vector<ll>>A;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    A.resize(N << 1);
    for (t = read(); t; --t)
    {
        d = -1;
 
        for (n = read(), i = 1; i <= n; ++i)c = read(), A[c].push_back(i), d = max(c, d);
 
        a = d;
 
        if (A[d].size() > 1)d = -1;
        else for (i = 0; i < d; ++i)if (A[i].size() < A[i + 1].size()) d = -1;
 
        if (d == -1) cout << -1 << endl;
        else
        {
          // cout << A[a].back() << endl;
 
            for (i = a - 1; i != -1; --i)
            {
                for (j = 0; j < A[i].size(); ++j)
                {
                    cout<<A[i].size()<<endl;
                    cout << A[i + 1][min(j, ll(A[i + 1].size() - 1))] << ' ' << A[i][j] << endl;
                }
 
            }
        }
 
        for (i = 0; i <= a; ++i)A[i].clear();
    }
    return 0;
}