算法1

算法1

(贪心+树形DP) $O(n)$

贪心思路：
我们要让前面的数尽量小，那么我们从1开始找，找到第一个出现1的节点n，说明我们要把1交换到n上。 一次交换能够影响到的范围肯定是与节点n相连的所有节点（以后简称影响区域）。

我们发现一个规律，当i < 1，intervals(i) = intervals(i - 1)，因为加入最新的数，数的范围不会变。当 i > 1，intervals(i) = intervals(i - 1) - 1 因为加上一个数字，数字的种类+1，影响区域就会减少1。

比如：
初始的intervals(1) = 1，表示整个序列都只有数字1，只能交换数字1，交换完后整个区域都有了数字1到t，intervals(2) = t - 1，表示这个时候，可以交换数字2了，交换完后，这个区域范围变成了1到t，数字1修改后又变成了2，数量变为0，影响区域就缩小了1。以此类推。

这样看下来，我们貌似可以根据交换序列从后往前遍历，然后根据交换序列进行更新即可。

由于更新的时候要在区间上进行DP，在树上，我们需要借用从叶子节点到根节点dfs的过程，先从叶子节点开始更新，因为根节点是整个区间的父区间，所以要从叶子节点计算出的区间来计算父区间。具体DP，我们在区间左边的影响区域我们可以通过左子树来更新，右边的区域通过右子树来更新。