[PKUWC2018] Minimax
考虑设 $f_{i, j}$ 表示 $i$ 号点的权值是全局第 $j$ 大的概率。
显然有转移方程：$f_{i, j} = \begin{cases} p_i & soncnt = 0 \\ f_{son, j} & soncnt = 1 \\ p_i \sum\limits_{k = 0}^{j - 1} (f_{lson, k} f_{rson, j} + f_{rson, k} f_{lson, j}) + (1 - p_i) \sum\limits_{k = j + 1}^{m} (f_{lson, k} f_{rson, j} + f_{rson, k} f_{lson, j}) & soncnt = 2 \end{cases}$（$soncnt$ 表示儿子个数，$m$ 表示叶子总个数）。
记 $pre_{i, j} = \sum\limits_{k = 0}^{j - 1} f_{i, k}, suf_{i, j} = \sum\limits_{k = j + 1}^m f_{i, k}$，则有当 $soncnt = 2$ 时，$f_{i, j} = p_i (f_{lson, j} pre_{rson, j} + f_{rson, j} pre_{lson, j}) + (1 - p_i) (f_{lson, j} suf_{rson, j} + f_{rson, j} suf_{lson, j})$
发现转移形式可以线段树合并，具体地，在合并同时维护 $pre, suf$ 数组，转移即可，由于转移式有乘积形式，为保证复杂度需要写乘法 $tag$。
[NOI2020] 命运
这题推导转移方程的思路有点妙。
首先有关键性质：对于 $Q$ 中的限制 $(u1, v)$ 与 $(u2, v)$，设 $dep_{u1} > dep_{u2}$，则如满足了限制 $(u1, v)$，则 $(u2, v)$ 一定满足。所以对于限制 $(u, v)$ 中 $v$ 相同的若干限制，只需关心 $u$ 深度最大的限制即可。
所以考虑设 $f_{i, j}$ 表示只考虑 $i$ 子树内的边的取值时（即钦定子树外的边全 $0$）与该子树有关的限制中未满足的限制的 $u$ 最深的深度为 $j$ 的方案数，特别地，$f_{i, 0}$ 表示无未满足的限制。
考虑往以 $i$ 为根的子树内添加一棵以 $u$ 为根的子树的情况，显然对于 $f_{i, j}$ 会更新为若干 $f_{i, x} f_{u, y}$ 的和的形式，按照边 $(i, u)$ 的权值分类讨论。
如果 $w_{(i, u)} = 1$，则 $u$ 子树的限制显然全都满足，所以对于并入 $f_{i, j}$ 的 $f_{i, x} f_{u, y}$ 有 $x = j$ 且 $y$ 任意，则 $f_{i, j} = f_{i, j} \sum\limits_{k = 0}^{dep_u} f_{u, k}$
如果 $w_{(i, u)} = 0$，则对于合并入 $f_{i, j}$ 的 $f_{i, x} f_{u, y}$，需要满足 $\max(x, y) = j$，则 $f_{i, j} = f_{i, j} \sum\limits_{k = 0}^{j} f_{u, k} + f_{u, j} \sum\limits_{k = 0}^{j - 1} f_{i, k}$
设 $g_{i, j} = \sum\limits_{k = 0}^j f_{i, k}$ 并将上述讨论合并则有转移方程 $f_{i, j} = f_{i, j} (g_{u, dep_u} + g_{u, j}) + f_{u, j} g_{i, j - 1}$。
考虑线段树合并转移，$g_{i, j}$ 可以在合并过程中用 [PKUWC2018] Minimax 的方法求出，直接合并即可。