题目链接：ARC 103D

你有一个长度为 $n$ 的序列 $D_1, D_2, \cdots, D_n$，所有的 $D_i$ 是两两不同的。是否存在一棵树满足如下条件？

• 节点从 $1$ 到 $n$ 标号，边从 $1$ 到 $n$ 标号。
• 对于每个节点 $i$，它到其他节点的距离之和为 $D_i$，注意每条边的长度都是 $1$。

如果存在这样一棵树，求出这棵树。

数据范围：$2 \le n \le 10 ^ 5$，$1 \le D_i \le 10 ^ {12}$。

Solution

注意到 $D_i$ 值最大的节点一定是叶子节点，它的子树大小为 $1$，这样我们可以通过点 $v$ 的 $D_v$ 值和其子树大小 $sz_v$ 求出父亲 $u$ 的 $D_u$ 值：

$$ D_u = D_v + 2 \times sz_v - n $$

那么我们可以找到对应的 $u$ 作为 $v$ 的父亲。我们只需要从大到小遍历 $D_i$ 序列然后一个个找到父亲就行了，注意在这个过程中需要更新父亲的 $sz$ 值。

为什么当前点 $v$ 的 $sz$ 值不会再被更新？这就需要我们证明：这样的遍历过程中一定满足 $D_u < D_v$。我们注意到 $D_i$ 值最小的点（最后一个点）一定是整棵树的重心，那么对于其他的非重心点一定有 $sz_i < \frac{n}{2}$（重心的性质）。于是我们得到 $D_u = D_v + 2 \times sz_v - n < D_v$，正确性得证。

最后再考虑一个问题：如果我们把所有的 $D_i$ 都更改一个相同的值，我们是无法判断出来的。于是我们要将整棵树遍历一遍，将重心的实际 $D_i'$ 值和给定 $D_i$ 值判断一下是否相等。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#define fail return puts("-1"), 0

const int N = 1e5 + 5, M = 2e5 + 5;

int n, tot, lnk[N], ter[M], nxt[M], sz[N];
long long dis[N], d[N];
std::map<long long, int> mp;

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dis[v] = dis[u] + 1;
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &d[i]);
        mp[d[i]] = i, sz[i] = 1;
    }
    int cnt = 0;
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        int v = it->second, u = mp[it->first + 2 * sz[v] - n];
        if (!u || u == v) fail;
        add(u, v), add(v, u), sz[u] += sz[v];
        if (++cnt == n - 1) break;
    }
    int rt = mp.begin()->second;
    dfs(rt, 0);
    if (std::accumulate(dis + 1, dis + n + 1, 0LL) != d[rt]) fail;
    for (int i = 1; i <= tot; i += 2) {
        printf("%d %d\n", ter[i], ter[i + 1]);
    }
    return 0;
}