给 Kaguya 看了一眼，Kaguya 用了一分钟切了。我看了一个小时。这就是神吗。
考虑一个点往叶子走答案的贡献，显然距离和会变化 \(-siz_u + (n - siz_u) = n - 2siz_u\)。如果我们以重心为根，那么所有的 \(n - 2siz_u > 0\)，那么这实际上是一个小根堆。
那么我们考虑从大往小枚举叶子，然后每次删去一个叶子。由于 \(d_i\) 互不相同，当前节点的父亲是可以唯一确定的。假如求出来的点不符合小根堆的性质就可以直接判无解。
当然这只考虑了差值合法，还需要考虑原值，所以构造完之后需要从 \(1\) 跑一遍看看答案是不是等于 \(d_1\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
long long d[MAXN];
vector<pair<long long, int>> q;
map<long long, int> mp;
int siz[MAXN];
int fa[MAXN];
vector<int> e[MAXN];
int dis[MAXN];
void dfs(int u, int pre) {
for (int v : e[u]) if (v != pre) {
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;
q.push_back({ d[i], i });
siz[i] = 1;
}
sort(q.begin(), q.end(), greater<>());
for (auto p : q) {
int u = p.second;
if (siz[u] == n) break;
long long d = p.first - (n - 2 * siz[u]);
if (mp.count(d) && d < p.first) {
fa[u] = mp[d];
siz[fa[u]] += siz[u];
} else {
printf("-1\n");
return 0;
}
}
for (int i = 1; i <= n; i++) if (fa[i]) {
e[i].push_back(fa[i]);
e[fa[i]].push_back(i);
}
dfs(1, 0);
long long tmp = 0;
for (int i = 1; i <= n; i++) {
tmp += dis[i];
}
if (tmp != d[1]) {
printf("-1\n");
} else {
for (int i = 1; i <= n; i++) if (fa[i]) {
printf("%d %d\n", i, fa[i]);
}
}
return 0;
}