题解 AT4434 【[ARC103D] Distance Sums】

~~md 这题 p 事真多~~ 一开始 WA 的一发，是因为我标号瞎给了，没注意这题还强制要你标号也对上 $D_i$。 --- 这题一看上去没啥思路的话，就先找些特殊的东西吧： $D_i$ 最大是啥？肯定是个叶子节点嘛。 $D_i$ 最小是啥？肯定是这棵树的重心嘛。 然后，我们再联想一些东西，~~比如，这题如果不定标号， SPJ 怎么写？（当时不知道定了标号还真是从这方面想想出来的）~~ 比如，怎么算一棵树的每个点到其他所有点的距离和？ $N^2$ 的东西太没技术含量了，而且对这个题的启发意义不大。有没有 $O(N)$ 的做法呢？ 我们假设以某个节点为根，先求出根的 $D_x$ 以及每个点的子树大小 $sz_x$。 然后考虑，如果知道一个点的 $D_x$，要计算它相连的一个节点的 $D_u$。不难发现有这样一个式子成立： $$D_u = D_x - sz_{u} + (N-sz_u) $$ 大概的意思是，你考虑「集合点」从 $x$ 放到了 $u$ 上之后，对于 $u$ 子树里头的点，都会少走一步；而对于不是 $u$ 子树里面的点，都会多走一步。 然后考虑这个东西和这个题的关联： 我们假设以重心为根节点，不难发现，在同一条链上的点，离重心越远，$D_i$ 就越大。 我们现在知道一个叶子节点的 $D_x$，也知道了它的子树大小为 $1$。这样我们就能反推其父节点的 $D_f$。 知道了 $x$ 的父亲节点 $f$。然后我们再找 $D_i$ 次大的点，这时候它的子树大小也一定知道了，也就能反推出它的父节点是啥。 这样一直反推上去就能建出一棵树。当然，如果中间的某一次反推中，找不到 $D_i$ 了，那么就说明这样的树不存在。 但是，这样反推出来的树，可能也不一定对。因为我们考虑我们反推的本质：用 $n-1$ 条边建立关于 $n$ 个变量的方程。我们固然能确定每对变量之间的关系，但是并不能确切的解出每个变量是不是等于这个值。 换句话说，我们只求出来 $D_i-D_j$ 都是满足于这棵树的，但是不知道 $D_i$ 是不是真的就是距离和。 要检查是不是满足也很简单，只需要确定一个 $D_i$ 是满足的，剩下的 $D_i$ 也就都满足了。 建出树后，要求一个 $D_x$ 很简单，DFS 一遍之后随便就求出来了。当然，我们用反推的时候求出来的 $sz_x$，将这些 $sz_x$ 加起来，求出重心的 $D_x$ 也是可行的。 $\rm Code$： ```cpp const int MAXN = 100010; struct Node { ll d; int id; Node() {} Node(ll d, int x):d(d), id(x) {} friend bool operator < (Node a, Node b) { return a.d < b.d; } }d[MAXN]; int sz[MAXN]; int u[MAXN]; int v[MAXN]; int main() { int n = ri; for(int i = 1; i <= n; i++) d[i] = Node(rl, i), sz[i] = 1; sort(d + 1, d + 1 + n); ll dis = 0, N = 0; for(int i = n; i > 1; i--) { ll D = d[i].d - n + (sz[i] << 1); int p = lower_bound(d + 1, d + 1 + n, Node(D, 0)) - d; if(d[p].d != D) return puts("-1"), 0; ++N; u[N] = d[i].id; v[N] = d[p].id; sz[p] += sz[i]; dis += sz[i]; } if(dis != d[1].d) puts("-1"); else for(int i = 1; i <= N; i++) printf("%d %d\n", u[i], v[i]); return 0; } ```