转载：

解题思路：

题目中强调的是移动，不能往里面添加，也不能从树中拿走。这个移动操作就给我们造成了一些困难，起初想一些 dp 的方法，感觉都不是很靠谱。

于是看了官方题解，题解中用了一步巧妙地转化，然后递归求解，很有借鉴意义。

首先对于移动操作次数最少，我们可以转化成，往树里插入 SUM 个点，尽量把点放入本来有苹果的位置，最大覆盖多少个的问题。那么原来没有苹果，现在要放点，这些位置的个数就是答案。

完成这一步转化之后就要挖掘题目性质，绝对值差 1 这个性质十分重要，因为这近似于一步二分，也就是如果我们从顶点开始递归地往下放，那么最多进行 log SUM 层就能使得剩下的可放点数达到 0 或 1，这就使我们得到一种很可行的分治求解的方法：Get(x, cnt) 表示向 x 这个点为根的子树中插入 cnt 个苹果，向空点放的情况最少有多少个（也就是移动次数最少有多少次）。对于 cnt 是偶数的情况，就直接 Get(x.left, cnt >> 1), Get(x.right, cnt >> 1), 而对于 cnt 是奇数，就要讨论一下左右放多放少这两种情况，取个 min 了。

递归的终止条件：

① cnt == 0，返回0

② x == 0 && cnt > 0 返回INF（无解）

③ cnt == 1 子树中本来有苹果返回 1，无苹果返回 0

P.S.题目中并没有给总点数，经过分析总点数不会超过叶结点的二倍。但是题目读入比较繁琐，字符串长度要开至少 5000。