花

注意到这个距离的定义类似曼哈顿距离，只是把 $+$ 变成了 $-$

联想到曼哈顿距离转切比雪夫距离，我们发现把坐标 $(x,y)$ 变为 $((x+y)/2,(x-y)/2)$ 后，两点之间的距离变为它们横坐标/纵坐标差值的较小值。

把横/纵坐标相同的并起来，分别沿着横坐标/纵坐标扫一遍，用每个横/纵坐标和之前一个距离不为 $0$ 的坐标的差更新最小值 再用同样方法扫一遍更新最小值的个数。

实现这种做法的最优复杂度是 $\Theta(n)$。

雾

考虑操作的性质其实是一某种方式遍历树花费的总距离，所以最小值是 $2$ 倍边数减去从 $1$ 出发最长的一条链长度（即根深度为 $0$ 定义下的树的深度）。

再考虑方案数，注意到进入一颗子树后必须经过所有节点才能出来（才能保证最小）。

考虑树形 DP，记录：进入一个子树经过所有节点再出来 和 进入一个子树经过所有节点 的方案数。

同时dp记录，进入一个子树经过所有节点再出来 的方案数的逆元，去掉一个快速幂的 $\log$。

时间复杂度 $\Theta(n)$。

雨

这道题等价与问你有多少组不同的不下降序列，最小值不小于 $x$，和为 $n$。

取 $m=\sqrt n$，把每组序列拆成 $2$ 部分，分别为不大于 $m$ 的数和大于 $m$ 的数。

先计算对于任意 $i\le n$，有多少组不同的不下降序列，满足最小值不小于 $x$，最大值不大于 $m$，和为 $n$。直接背包 DP 即可。

再计算对于任意 $i\le n$，有多少组不同的不下降序列，最小值不小于 $\max(x,m+1)$，和为 $n$。

考虑 $dp(i,j)$ 表示有多少组不同的不下降序列，最小值不小于 $\max(x,m+1)$，和为 $n$，长度为 $j$。

$dp(i,j)$ 向 $dp(i+j,j)$（每个数 $+1$）和 $dp(i+\max(x,m+1),j+1)$（头上添加一个数 $\max(x,m+1)$）转移即可。

最后将 $2$ 部分的答案进行卷积，即得到最终答案。

时间复杂度 $\Theta (n\sqrt n)$。