不太了解这个东西的具体定义是什么，总之应该是一个用数据结构维护 DP 状态的某几个维度的 trick 吧。

事实上你可以把这篇 post 理解为三个题的解集。

先直接来看 noi2020 - Destiny 这个题。

给定一棵树 $T = (V, E)$ 和点对集合 $\mathcal Q \subseteq V \times V$ ，满足对于所有 $(u, v) \in \mathcal Q$，都有 $u \neq v$，并且 $u$ 是 $v$ 在树 $T$ 上的祖先。其中 $V$ 和 $E$ 分别代表树 $T$ 的结点集和边集。求有多少个不同的函数 $f$ : $E \to \{0, 1\}$（将每条边 $e \in E$ 的 $f(e)$ 值置为 $0$ 或 $1$），满足对于任何 $(u, v) \in \mathcal Q$，都存在 $u$ 到 $v$ 路径上的一条边 $e$ 使得 $f(e) = 1$。由于答案可能非常大，你只需要输出结果对 $998,244,353$（一个素数）取模的结果。

我们略过 DP 的过程，直接给出其定义 $f(x,j)$ 表示考虑子树 $i$，限制条件的 $v\in{\rm subtree}(x)$ 且限制 $(u,v)$ 尚未被满足，$u$ 的深度最深且 $j={\rm dep}(u)$ 的不同映射 $f:E_{{\rm subtree}(x)}\rightarrow\{0,1\}$ 数量，以及其转移$f(x,i)= f(x,i)\sum\limits_{y\in{\rm suf}(x)}\left(\sum\limits_{j=0}^{{\rm dep}(x)}f(y,j)+\sum\limits_{j=0}^{i}f(y,j)\right)+f(y,i)\sum\limits_{j=0}^{i-1}f(x,j)$。

令 $g(x)$ 为 $f(i)$ 的前缀和，得到平方级算法。

如果我们考虑把 DP 的第二维度状态放到线段树上，那么子树的合并就可以放到线段树上去做，即使用线段树的合并 trick 来做 DP。

我们来看看合并的具体过程。贴近实现，我们令 ${\rm merge}:\{(x,y,l,r,s_x,s_y)\}\rightarrow{\rm node}$ 表示线段树合并的过程，其中 $s_x$ & $s_y$ 表示 DP 的前缀和（即 $g$），在实现（以及下文的讲解）中，均把这两个变量视作别名。

有这样几种情形需要探讨。

• $l=r$：此时应该把 $f(y,l)$ 合并到 $f(x,l)$ 中，直接对线段树结点维护的 DP 值进行修改；
• $x=\Omega$：此时 $f(x)$ 的 DP 值并没有意义，在本题中可以视作零。于是打乘法标记即可；
• $y=\Omega$：与上一条类似。

于是得到解决，参考实现。

再来看 pkuwc2018 - Minimax 这个题。

给出一棵有 $n$ 的结点的二叉有根树，并给出其叶子结点的权值，对于一个非叶子结点，其权值有 $p_i$ 概率取得儿子中的最大值， $1-p_i$ 的概率取得最小值。

令 $\{v_{i}\}$ 表示最终根结点（$1$-th 结点）的所有可能取值（升序排列），其个数记为 $m$，每一个 $v_i$ 取得的概率记为 $r_i$，将其按照 ${\rm hash}(i)=i\times v_i\times r_i$ 的规则求出 $\sum_i{\rm hash}(i)$。

与上一题类（完 全）似（一 致）地，同样略过 DP 的过程，给出其定义 $f(i,j)$ 表示结点 $i$ 取得值 $j$ 的概率，以及其转移 $f(i,j)=\sum\limits_{v\in{\rm suf}(i)} f(v,j)\left(p_i\sum\limits_{1\leqslant k<j}f(v',k)+(1-p_i)\sum\limits_{j<k}f(v',k)\right)$，其中 $v'$ 表示 ${\rm suf}(i)\setminus\{v\}$ 中的唯一取值。

令 $g(i)$ 为 $f(i)$ 的前缀和（显然这里的 $\infty$ 并不是「真正的无限」），得到平方级的算法。

同样考虑把 DP 的第二维度状态放到线段树上，在线段树合并时维护 $s_x$ & $s_y$ 表示 DP 的前缀和，直接维护即可。

参考实现。

最后来看到 codeforces - 671D / Roads in Yusland。

给定一棵 $n$ 个点的以 $1$ 为根的树。有 $m$ 条路径 $(x,y)$，保证 $y$ 是 $x$ 或 $x$ 的祖先，每条路径有一个权值。你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。

这题的平方 DP 都有一定难度……看了 duyi 的题解挺久才理解……不过如果做过 noi2020 - Destiny 的话应该会好很多。

称 ${\rm route}(u,v)$ 中的 $u$ 为起点，$v$ 为终点，在 $v$ 决策一个 route 是否被选择。参考 noi2020 - Destiny 的状态设计，令 $f(x,i)$ 表示在 ${\rm subtree}(x)$ 中选择了若干 routes，其中终点深度最深并且高于 ${\rm dep}(x)$ 的深度为 $i$ 的最优方案。

转移即 $f(x,i)=\min\limits_{y\in{\rm suf}(x)}\{f(y,i)+\sum\limits_{z\in{\rm suf}(x)\setminus\{y\}}g(z)\}$，其中 $g(x)=\min\limits_{1\leqslant i<{\rm dep}(x)}\{f(x,i)\}$，还需要考虑每条 route 带来的额外转移，转移式显然不赘。这些 transforming formulae 也许带有一些构造成分在里面，至少我觉得不太自然……

然后考虑线段树合并优化，你需要支持区间增量 & 全局查询最小值 & 合并（与此同时区间取 $\min$）& 单点取 $\min$。因为 $O((n+m)\log_2n)$ 的空间复杂度并不能通过此题。

考虑以时间换空间，我们采用权值平衡树 & 启发式合并来解决（参考实现中给出的是 std::set）。

平衡树上每个结点维护一个 2-tuple $(i,f(x,i))$，以第一关键字排序。我们依次考虑如何支持上文的操作。

• 区间增量：如果及时把 $i>{\rm dep}(x)$ 的元素弹出，这就变成了全局增量，直接维护即可；
• 全局查询最小值：这个是本题最妙的地方，因为关键字的选取，平衡树无法简单地取出最小值，我们需要更多的性质。注意到 $\forall j<k,s.t.f(x,j)<f(x,k)$，此时的 $k$ 都是无用的，可以直接删除，这得出了此题的单调性。如此全局最小值就是平衡树上最右边的结点；
• 合并：启发式合并即可；
• 单点取 $\min$：相当于插入操作，直接来即可，需要注意一些不是特别细的细节（雾）。

如此时间复杂度退成了 $O((n+m)\log_2^2n)$，但是空间复杂度优化到了 $O(n+m)$，可以通过此题。

参考实现。