点分治爆栈祭.
$phantasm$
将每次选择的位置看成一个数列,第一个位置必定是 $1$ ,所以只需要求出它的差分序列方案数.
差分序列中共 $m-1$ 个元素,每个元素必须 $\le k$ ,总和为 $n-1$ .
调整一下后用隔板法处理,答案是组合数,在模 $2$ 意义下,根据 $Lucas$ 定理,只需判断二进制位即可.
$skylines$
直接大力点分治预处理所有点的答案.
枚举子树时正反顺序都做一次,再考虑上分治中心.
时间复杂度 $O(n\log n+T)$ .
$kiseki$
题面写得太垃圾了.
每次从已有的数中选一个,得到它的权值,并获得它的后继,存档可以重复获得.
考虑 $dp$ ,状态只与当前有的存档集合有关,与顺序无关.
而从小到大排序后,相邻两项的差分值只可能是 $0/1$ ,所以可以用一个二进制数 $S$ 来记录.
设 $f(i,S)$ 表示有 $i$ 个存档,差分值的状态是 $S$ 的方案数,转移时枚举增加的存档.
总方案数是 $m!$ ,预处理差分状态 $S$ 对应的序列权值是 $val(S)$ ,答案就为
$$
\sum_{S} \frac {f(m,S)} {m!} \cdot val(S)
$$
时间复杂度 $O(m\cdot 2^m)$ .