Link
对多叉堆组合计数的理解加深了！
观察操作 1：将 \(x\) 所在树的 根 直接接在 \(y\) 所在树 树根 之下。感性理解一下，树合并之后的形态是类似的，也就是说更新完祖先的值之后自身不会有任何的变动。并且答案只和祖先有关，在祖先操作，在祖先统计。这部分可以用并查集来实现，合并时更新 \(siz()\) 和计数答案 \(f()\) 即可。各个儿子都是独立的，彼此之间不会产生答案的贡献干扰。
考虑怎么应对操作 2：注意到此时的根只能填写 \(0\)，考虑合并时怎么更新我们维护的这个答案 \(f\)。给出式子：
\[f(y)' = f_x \times f_y \times \binom{siz(x) + siz(y) - 1}{siz(x)}
\]
注意到我们只关心儿子相对于父亲的值大小关系，所以原来 \(x, y\) 为根的子树所有合法的方案（即独立时 \(x, y\) 的方案组合）都可以组合起来形成新树的部分合法方案，合并后新树的总节点数为 \(siz(x) + siz(y)\)，\(y\) 的根节点必须是 \(0\)，剩下的从 \(siz(x) + siz(y) - 1\) 中选择 \(siz(x)\) 个节点分配给子树 \(x\)，其余位置分配给 \(y\)，相当于“插入”，同时保证堆序。
一个有趣的视角是从组合数学对于堆性质树的限制：
\[f_u = \frac{siz(u)!}{\Pi_{v} siz(v)}
\]
随着节点数的增加，方案数自然增加，我们在 \(x, y\) 中的子树可以填充的选项也变多了，这方面的限制由组合数决定。一个很有可能的疑点是：\(f(x), f(y)\) 都只是 \(x, y\) 子树内部的权值分配而不是合并后的全局分配，组合数正是用于处理这个新全局的权值分配问题。