标签 重心 下的文章

「ARC 103D」Distance Sums

题目链接：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}$。

「算法笔记」点分治