换根 DP 模型
stripe_python
·
·
算法·理论
换根 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} 表示 u 不为中点的最大得分,f_{1,u} 表示 u 确定为中点的最大得分。这些 DP 值都仅考虑 u 子树内部的边权。
以中点为主体的原因是,树上不存在 X 形结构,故中点对应的三点链是确定的。
-
求解 f_{0,u} 时,分讨儿子 v 的选择可得 f_{0,u}\gets \max(f_{0,v},f_{1,v}+w(u,v))。转移 \gets 是求和。
-
求解 f_{1,u} 时,需要选定儿子 v 并配对 \text{fa}(u) \to u\to v,贡献 w(u,v)。
设最优转移 a_v=\max(f_{0,v},f_{1,v}+w(u,v)),钦定 v 为延伸位置,转移为
f_{1,u}=\max_{v \in \text{son}(u)} \left(f_{0,v}+\sum_{x\in \text{brother}(v)} a_x\right)
-
DP 初值为叶节点 f_{0,u}=0, f_{1,u}=-\infty。
-
答案为 f_{0,\text{root}}。
对二元组 (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)。代码。
:::::