当前位置：首页 > news >正文

【动态规划】树上连通块计数

news 2025/8/3 21:33:29

$\sum\limits_{\mathbb{V}}1$。

类似于树上点对贡献。

在连通块中深度最小的点处进行统计。

下面简记“连通块中深度最小的点是点u的连通块”为“以点u为根的连通块”。

$f_u$：当前已统计的以点u为根的连通块的个数。

转移：在遍历到点u的一个儿子点v时，情况分为删除边(u,v)和不删除边(u,v)，$f_u=f_u*1+f_u*f_v$。

边界：$f_u=1$。其他为0。

$ANS=\sum\limits_uf_u$。

补充：另一种dp设计：$f_{u,d}$：考虑了以u为根的子树，当前u所在连通块的根的深度为d，……。

$\sum\limits_{\mathbb{V}}w(\mathbb{V})$。

类似于《7.4.5.3.1.树上连通块计数》。

所有连通块大小的乘积=在每个连通块内恰好选一个点的方案数。dp多开一维0/1表示当前连通块有/无选关键点。

$\sum\limits_{\mathbb{V}}\sum\limits_{u\in\mathbb{V}}a_u$。

$f_u$：当前已统计的以点u为根的连通块的个数。

$g_u$：当前已统计的以点u为根的连通块内的点的贡献。

转移：在遍历到点u的一个儿子点v时，情况分为删除边(u,v)和不删除边(u,v)，

边界：$f_u=1,g_u=a_u$。其他为0。

$ANS=\sum\limits_ug_u$。

$\sum\limits_{\mathbb{V}}\sum\limits_{u,v\in\mathbb{V}}(a_u\oplus a_v)$，其中⊕满足对加法的分配律。

异或：拆位，转化为1的个数与0的个数的乘积，即可满足对加法的分配律。

结合《7.4.5.1.树上点对贡献》和《7.4.5.3.3.树上连通块内点贡献》。点对仍在点对的lca处进行统计，借助树上连通块的转移将点对贡献到其所属的所有连通块。

$f_u$：当前已统计的以点u为根的连通块的个数。

$g_u$：当前已统计的以点u为根的连通块内的点的贡献。

$h_u$：当前已统计的以点u为根的连通块内的点对的贡献。

转移：在遍历到点u的一个儿子点v时，情况分为删除边(u,v)和不删除边(u,v)，

$h_u=h_u*1+(h_u*f_v+h_v*f_u+g_u\oplus g_v)$。

当不删除边(u,v)时，统计到含点u和点v的连通块，情况分为点对都在当前以点u为根的连通块（$h_u*f_v$）、点对都在以点v为根的连通块（$h_v*f_u$）和点对分别在当前以点u为根的连通块和以点v为根的连通块（$g_u\oplus g_v$）。
$g_u=g_u*1+(g_u*f_v+g_v*f_u)$。
$f_u=f_u*1+f_u*f_v$。

边界：$f_u=1,g_u=a_u,h_u=0$。其他为0。

$ANS=\sum\limits_uh_u$。

在dp中，(i,j)与(j,i)视为相同，不会重复计算。根据题意(i,j)与(j,i)是否算不同的贡献，判断最终答案是否要乘2。

$\sum\limits_{cnt_\mathbb{V}(\mathbb{G})=m+1}\sum\limits_{\mathbb{V}\in\mathbb{G}}\sum\limits_{u,v\in\mathbb{V}}(a_u\oplus a_v)$，其中⊕满足对加法的分配律。

$f_{u,j}$：在以点u为根的子树内，当前已删除了j条边，已统计的以点u为根的连通块的个数。

$g_{u,j}$：在以点u为根的子树内，当前已删除了j条边，已统计的以点u为根的连通块内的点的贡献。

$h_{u,j}$：在以点u为根的子树内，当前已删除了j条边，已统计的所有连通块内的点对的贡献。

$bf_j,bg_j,bh_j$：$f_{u,j},g_{u,j},h_{u,j}$的备份数组。备份后$f_{u,j},g_{u,j},h_{u,j}$清零。

转移：在遍历到点u的一个儿子点v时，

删除边(u,v)，
- $h_{u,j+k+1}←bh_j*f_{v,k}+h_{v,k}*bf_j$。
- $g_{u,j+k+1}←bg_j*f_{v,k}$。
- $f_{u,j+k+1}←bf_j*f_{v,k}$。
不删除边(u,v)，
- $h_{u,j+k}←bh_j*f_{v,k}+h_{v,k}*bf_j+bg_j\oplus g_{v,k} $。
- $g_{u,j+k}←bg_j*f_{v,k}+g_{v,k}*bf_j$。
- $f_{u,j+k}←bf_j*f_{v,k}$。