ARC103D Distance Sums

题意：有一棵 个点的树，每条边的长度均为 。

给出 个互不相同的数 ，表示树上的节点 到其他所有点的距离和。

构造一棵符合要求的树，或指出无解。

，时限 。

---

先考虑给出一棵树如何计算 。

可以换根 ：

对于相邻的点 ，记 表示以 为根时 的子树大小。

考虑 。对于 代表的点，到 的距离比到 的距离大 ，对于 代表的点，到 的距离比到 的距离小 。

故有：

首先有结论： 最小的 是整棵树的重心。

我们进一步研究 的结构。

首先有经典的结论： 最小的 是重心。

若以重心为根，节点 为节点 的父亲。观察式子：

根据重心的性质， ，故 。

也就是说，以重心为根时， 由浅到深单调不降。

---

回到本题。

我们将 从大到小排序，这样父亲一定在儿子后面。

按照 从大到小的排序考虑各个点。这时该点的子孙都已经被考虑过了，所以该点的子树大小是确定的。

根据子树大小 和 ，就能得到 。

本题保证了 互不相同，于是直接（二分）查找符合条件的点即可。若找不到，则无解。

最后，我们上述构造只是保证了所有的 是合法的。所以还需任选一个 验证是否合法。

复杂度 。