换根 DP 模型

· · 算法·理论

换根 DP 不知道咋避免逆元,我得滚回普及组重修了。

设信息集合 S 上有合并运算 \oplus,代数结构 (S,\oplus) 是交换幺半群,单位元为 e。节点 u 的基础信息为 a_u。

对有向边 u \to v 定义变换 T_{v \to u} 表示将 v 为根的信息转换为 v 对 u 的贡献。

钦定一个初始根 \text{root},设 f_u 为 u 为根的子树 DP 值,转移为

f_u=a_u \oplus\bigoplus_{v \in \text{son}(u)} T_{v\to u}(f_v)

自底向上进行 DFS 即可求出以 \text{root} 为根的答案 f。

换根 DP 解决的问题是:对每个 u=1,2,\cdots,n 求出以 u 为根的答案 \text{ans}_u。

我们自顶向下 DFS。将断开 u \to \text{fa}(u) 边时,父亲所在连通块以 \text{fa}(u) 为根的 DP 值经过 T_{\text{fa}(u) \to u} 变换后,得到的信息记作 g_u。初始 g_{\text{root}} 为单位元 e。答案 \text{ans}_u=f_u \oplus g_u。

将 u 的儿子排列为 v_1 \sim v_k。维护前后缀贡献

\text{pre}_i=\bigoplus_{j \le i} T_{v_j \to u} \left(f_{v_j}\right)\\ \text{suf}_i=\bigoplus_{j \ge i} T_{v_j \to u} \left(f_{v_j}\right)

约定 \text{pre}_0=\text{suf}_{k+1}=e。

对儿子 v_i,先合并除 v_i 方向外的信息,再传递给 g_{v_i} 得到

g_{v_i}=T_{u \to v_i}\left(a_u \oplus g_u \oplus \text{pre}_{i-1} \oplus \text{suf}_{i+1}\right)

认为信息复合是 O(1) 代价,总复杂度 O(n)。

实际做题的时候,我们一般先写 DP 再换根,套用上面的模型,难点就变成了如何从 DP 式中推出 \oplus 和 T。一般 T 是考虑单个儿子的贡献,而 \oplus 则去研究两个儿子的合并。

AT_dp_v Subtree

给定一棵 n 个节点的无根树。对每个 u=1,2,\cdots,n 求出,包含 u 的树上连通块数目。

对给定的模数 m 取模,不保证 m 为质数。

:::::success[题解]

设 f_u 表示仅考虑 u 子树,且 u 强制选入连通块的方案数。每个子树可选可不选,转移

f_u = \prod_{v \in \text{son}(u)} (1+f_v)

自顶向下换根 DP,初始 g_u=1。代数结构是交换幺半群 (\mathbb{Z}_m , \times),变换 T_{u \to v}(x)=1+x。

将 u 的儿子排列为 v_1 \sim v_k,维护前后缀积

\text{pre}_i=\prod_{j \le i} (1+f_{v_i})\\ \text{suf}_i=\prod_{j \ge i} (1+f_{v_i})

对儿子 v_i 的转移为

g_{v_i}=1+g_u \times \text{pre}_{i-1} \times \text{suf}_{i+1}

答案是 f_ug_u。复杂度 O(n)。代码。

:::::

P3647 [APIO2014] 连珠线

按照下述方式构造一棵无根树:每轮添加 \{1,2,\cdots,n\} 中未添加的某点 w,选定两种操作之一:

  • 选定已添加的点 u,连红边 u \leftrightarrow w。
  • 选定已添加的点 u,v,且 u \leftrightarrow v 是红边,删去 u \leftrightarrow v 边后连接蓝边 u \leftrightarrow w 和 v \leftrightarrow w。

给定树的最终形态,边的颜色未知。定义得分为蓝边边权和,在所有可能的构造方法中,最大化得分并输出。

:::::success[题解]

连红边相当于挂叶子,连蓝边是在父子节点间插入新点。

我们枚举第一轮添加的节点定根,可以证明,所有蓝边三元组 (u,w,v) 都是 \text{fa}(u) \to u\to \text{son}(u) 的三点共线结构。问题转化为,将树剖成若干祖先—后代三点链,最大化链上边权和。

钦定一个根节点,列出树形 DP:

对二元组 (f_{0,u},f_{1,u}),合并操作

(x_0,x_1) \oplus (y_0,y_1)=(x_0+y_0, \max(x_1+y_0,x_0+y_1))

转移 \max(x_1+y_0,x_0+y_1) 的意思是,选定恰好一个点作为三点链的较深边端点,不能两侧同时选择。

这是交换幺半群信息,叶子处单位元 e=(0,-\infty)。

边 u\to v 将儿子 v 的 DP 信息转换为贡献

T_{v \to u} (f_v)=(\max(f_{0,v},f_{1,v}+w),f_{0,v}+w)

完全套用换根 DP 模型即可。复杂度 O(n)。代码。

:::::