[ARC103D] Distance Sums

arc 题号很神奇...以链接中的为准。

题解

给点 \(i\) 一个权重 \(w_i\),重新定义 \(D_i = \sum_k w_k dis(i,k)\)。初始时对于所有的 \(i\)\(w_i = 1\)。任意时刻,\(\sum_i w_i = n\)

可以发现,如果点 \(v\) 与点 \(u\) 相邻,以点 \(u\) 为根时点 \(v\) 的子树中的点权重之和为 \(s\),则 \(D_v - D_u = n - 2s\)

找到 \(D_u\) 最大的点 \(u\),由于任何与 \(v\) 相邻的点都满足 \(D_v - D_u \le 0\),所以以 \(u\) 为根 \(v\) 子树中的点权重和至少为 \(\frac n 2\),所以 \(u\) 至多有一个相邻点。我们不考虑 \(n = 1\) 的情况。\(u\) 是一个叶子。

假设与 \(u\) 相邻的点是 \(f\),那么 \(D_f-D_u = 2w_u - n\),由于 \(D_i\) 互不相同,这就唯一确定了 \(u\) 的父亲 \(f\)。我们记录一下点 \(u\) 和点 \(f\) 连一条边,把点 \(f\) 的权重加上点 \(u\) 的权重,然后把点 \(u\) 删去。这样对还在树上的任何一个点 \(i\),经过这次操作 \(D_i\) 恰好减少了 \(w_u\)。更新一下即可。

一直这样操作下去就唯一确定了一棵树,检验一下即可。(懒得判特殊情况,就直接暴力验证了)

实际上不需要更新 \(D_i\),因为所有的操作都是整体加,而我们始终只会用到 \(D_i\) 的相对大小关系和 \(D_f-D_u\) 的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

typedef long long ll;

priority_queue<ll> pq;
map<ll, int> mp;

int n, l[maxn], dep[maxn], sz[maxn], w[maxn], vis[maxn], e_u[maxn], e_v[maxn], tot, e = 0;
ll D[maxn], S[maxn];

struct Edge {
int v, x;
} E[maxn];

inline void addEdge(int u, int v) {
E[e].v = v; E[e].x = l[u]; l[u] = e++;
}

void dfs1(int u) {
sz[u] = 1;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
}
}

void dfs2(int u) {
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
S[v] = S[u] + n - 2 * sz[v];
dfs2(v);
}
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &D[i]);
for (int i = 1; i <= n; i++) {
mp[D[i]] = i;
pq.push(D[i]);
w[i] = 1;
}
vis[0] = 1;
while (pq.size() > 1) {
ll v = pq.top(); pq.pop();
int u = mp[v];
vis[u] = 1;
if (!vis[mp[v + 2 * w[u] - n]]) {
int t = mp[v + 2 * w[u] - n];
w[t] += w[u];
addEdge(t, u);
++ tot;
e_u[tot] = t; e_v[tot] = u;
} else {
puts("-1");
return 0;
}
}
int r = mp[pq.top()];
dfs1(r);
for (int i = 1; i <= n; i++) S[r] += dep[i];
dfs2(r);
for (int i = 1; i <= n; i++) {
if (S[i] != D[i]) {
puts("-1");
return 0;
}
}
for (int i = 1; i <= tot; i++) printf("%d %d\n", e_u[i], e_v[i]);
return 0;
}