随便写一些算法（五）

树上dp有关的技巧

问题描述，在一棵树上给定一些路径，每一条路径对应一个权值，现在需要选出一些路径
使得这些路径不相交，并且权值和最大

算法分析
树形 $\text{dp}$ 的时候，考虑每一个点，因为每一个点有路径限制，一个点最多只能在一条路径上（也可能不在任何一条路径上）
所以尝试把在哪一条路径加入 $\text{dp}$ 的维度

$dp(i, j)$ 表示点 $i$ 在路径 $j$ 上，子树能取到的最大权值，其中 $j = 0$ 对应没有路径穿过 $i$
$i$ 的儿子记为 $\{v_1, \cdots, v_m\}$

特别地，这里定义路径贯穿 点 $u$ ，指存在路径从 $u$ 往它的父节点伸出来

对于 $j \neq 0$ ，那么有路径贯穿 $i$ ，不妨设路径 $j$ 贯穿了 $i$ 的儿子 $v_k$ ，那么其他儿子
$\{v_1, \cdots, v_{k-1}, v_{k+1}, \cdots\}$ 是不能有路径贯穿的，可以再定义一个状态 $f(u)$
表示 $u$ 这个节点没有路径贯穿的时候，能取到的最大权值，这样就可以写出转移方程
$\displaystyle dp(i, j) = \left(\sum_{v \neq v_k} f(v) \right) + dp(v_k, j)$
对于 $j = 0$ ，那么 $dp(i, 0) = \displaystyle \sum_{v} f(v)$
接下来考虑计算 $f(u)$ ， $f(u)$ 也有两种情况，一种是 $u$ 不在任何一条路径上
第二种是 $u$ 处在某条路径的最高点

算法分析2
注意到给一条树上路径 $(u, v, w)$ ，表示从 $u\to v$ 存在一条权值为 $w$ 的路径
注意到树上路径形式是 $u \to \text{LCA} \to v$ ，这启发我们在 $\text{LCA}$ 处来考虑这个问题

定义 $dp(u)$ 表示 $u$ 作为 $\text{lca}$ 时， $u$ 及其子树能够选择的最大不相交路径权值
其中，作为 $\text{lca}$ 的意思就是说所选择的路径，不能伸出 $u$ ，不能从 $u$ 往其祖先延伸

这样，就可以分为两类来讨论

第一是不选经过 $u$ 的路径 $x \to u \to y$ ，其中 $u = \text{lca}(x, y)$
这样 $dp(u) = \displaystyle \sum_{v \in \text{son}(u)} dp(v)$ ，这一部分可以记为 $sdp(u)$
第二就是选经过 $u$ 的路径，此时对于 $x \to u \to y$ 所有的点 $v$ ，不能考虑 $dp(v)$
而应该考虑把 $v$ 这个点删除后，剩下 $v$ 的子树构成的森林的 $dp$ 值的和，换句话说
对于路径 $x \to u \to y$ 的所有点 $v$ ，此时需要考虑 $\displaystyle \sum_{v \in \text{path}} dp(\textbf{son}(v))$