这也太难了！这也太难了！这也太难了！
A UOJ-607 UR#20 跳蚤电话
加点操作太抽象，改成删点，每次可以删一个叶子，或者删一个只有一个父亲和一个儿子的节点。
算方案还带顺序，子树间再算多重集组合数不方便，不如直接算任意顺序删点最后合法删完的概率。
设 \(f_u\) 为按任意顺序删点删完 \(u\) 子树的概率，答案就是 \((n-1)!\prod_{u\in \mathrm{son}(1)} f_u\)。
暴力转移枚举子树内最晚删的点，如果就是 \(u\) 本身，那么贡献是 \(\prod_{v\in \mathrm{son}(u)} f_u\)。
反之枚举一个 \(v\)，这时就要先删 \(v\) 子树内其他节点和不在 \((u,v)\) 路径上的子树，设 \((u,v)\) 路径为 \(a_1=u,\cdots,a_l=v\)，那么 \(a_k\) 除 \(a_{k+1}\) 以外的其他子树合法条件就是这些子树本身能完全删除，同时 \(a_k\) 在这些节点之后删除，和上面合起来就是：
\[f_u=\dfrac{1}{siz_u}\left(\prod_{v\in \mathrm{son}(u)} f_v+\sum_{v\in \mathrm{subtree}(v),v\neq u} \prod_{w\in \mathrm{son}(v)} f_w\prod_{k=1}^{l-1} \dfrac{1}{siz_{a_k}-siz_{a_{k+1}}}\prod_{w\in \mathrm{son}(a_k),w\neq a_{k+1}} f_w\right) \]设 \(g_u=f_u\times siz_u\)，就把外面的系数摘掉了，注意到前半部分复杂度正确，后半部分和 \(u\) 有关的只有 \(a_1\) 一项，于是相当于是 \(v\) 对 \(u\) 做贡献，每次合并就是增加一项。
这样就是：
\[g_u=\prod_{v\in \mathrm{son}(u)} f_v+\sum_{v\in \mathrm{son}(u)} g_v\times \dfrac{1}{siz_u-siz_v}\prod_{w\in \mathrm{son}(u),w\neq v} f_w \]实际上，\(f\) 前半部分乘上这一项系数之后就和 \(f\) 后半部分形式相同，所以转移是正确的。
提交记录：Submission - UOJ
D CodeForces-CF1239E Turtle *3100
这个东西长得很想皇后游戏那题。
考虑交换贪心，若只交换 \(a_{x,1}\) 与 \(a_{x+1,1}\)，则在 \(x+1\) 位置向下的值路径和不变，在 \(x\) 位置向下的路径和由 \(a_{x,1}\) 与 \(a_{x+1,1}\) 的大小决定，因此第一行应当是一个单调不降的序列，而第二行应当是一个单调不升的序列。再考虑两条相邻路径对应权值的变化量，实际是增加 \(a_{x+1,1}\)，减少 \(a_{x,2}\)，由于 \(a_{x,1}\) 不降，\(a_{x,2}\) 不升，所以这个变化量 \(a_{x,1}-a_{x+1,2}\) 应当是单调不降的，因此其原函数是下凸或是单调函数，也就是只有在 \(1\) 或 \(n\) 位置向下走才会取到最大值。
把两个最小值放在 \(a_{1,1},a_{n,2}\) 处，剩下就是要规划分配方案使得二者中最大值最小了，背包就可以解决问题，输出方案只需要按前面单调的性质排布。复杂度是 \(O(n^3\omega)\)。
标签：子树,乱写,siz,多校,son,prod,杂题,单调,mathrm From： https://www.cnblogs.com/SoyTony/p/Multiple_School_DP_Training_Problems_in_Xian_June.html