题解 CF1286B 【Numbers on Tree】

· · 题解

首先，我们考虑无解的情况，很明显，当有一个点的c_i要大于等于这个点的字数大小时，肯定无解。否则，当每个节点的值不同时，一定有解，证明显然。

题目中的限制是每个数在1 ~ 10^9之间，但是没有意义，可以离散化变成1,2,\cdots,n的（虽然说我直接构造1~n了）。注意到这一题的权值与答案没有关系，我们所需的仅仅只是在每个权值不同时它们之间的大小关系。

很明显，叶子节点之间的大小关系时不影响答案的，那么我们可以给叶子节点之间的大小随便选。那么对于每一个非叶节点来说，在它的子树之间的大小全部被处理出来时，它只需要在将子树中的两个点拿出来，将自己的权值放在它们之间就可以了。

如果一开始就给节点赋值，最后很有可能会导致某个节点插在了两个相邻的权值之间，会出现浮点数，这很讨厌，所以，我们一开始不给节点赋值，只考虑维护权值之间的大小关系。

思考一种能够维护数列大小关系的数据结构，支持动态插入一个元素，要求插入时间复杂度不超过O(n)，查找时间复杂度不超过O(n)，这样的数据结构一个都想不出来就退役吧，我们有三个候选数据结构，分别是：

  1. 数组，单次插入O(n)，单次查找O(logn)
  2. 链表，单次插入O(1)，单次查找O(n)
  3. 平衡树，单次插入O(logn)，单次查找O(logn)

我选用的是第二种，因为我觉得在动态插入时，链表更加直观。

所以到这里，思路就很清晰了，先将所有叶子节点用链表链接起来，然后考虑它们的父亲插在哪儿，再往上推一层，……，这样下去，就可以得到所有节点之间的大小关系，然后，遍历一遍链表，按大小关系赋值即可，时间复杂度O(n^2)。

代码可以去我的博客查看：Codeforces 1286B. Numbers on Tree题解