AT_dp_v — Subtree

思路

给树上的每个点染黑/白，要求黑色点集连通。对每个点 $v$，问以 $v$ 为黑点的染色方案数 $modM$。

这是经典的 换根 DP。

一次换根 DP（down）

任取根 $1$，做自底向上 DP。定义：

$$\text{down}[u]=\text{以 }u\text{ 为根的子树上，}u\text{ 为黑且黑色点集连通的方案数}$$

若某个孩子 $c$ 是白色，则 $c$ 的整个子树必须全白（否则出现断开在子树里的黑点），贡献因子 $1$；若 $c$ 是黑色，则贡献 $\text{down}[c]$。所以：

$$\text{down}[u]=\prod _{c\in \text{children}(u)}(\text{down}[c]+1)$$

叶子 $\text{down}=1$。

二次换根（up）

答案 $\text{ans}[u]$ 是把 $u$ 当作根时，全部邻居分支的乘积。它等于：

$$\text{ans}[u]=\text{down}[u]\cdot (\text{up}[u]+1)$$

其中 $\text{up}[u]$ 表示「$u$ 指向其父边那一侧（切掉边后包含父节点的分量）」里，父方向分支的贡献值。对根设 $\text{up}[1]=0$（没有父侧，因子为 1，不影响）。

自顶向下计算孩子 $u$ 的 $\text{up}$：

$$\text{up}[u]=\prod _{w\in \text{neighbors}(p),w\ne u}(\text{branch}(w,p)+1)$$

即「父节点 $p$ 除 $u$ 外的所有邻居分支值 +1 相乘」。对孩子算子分支用 $\text{down}$，对 $p$ 的父侧用 $\text{up}[p]$。

关键点：不能直接除

$M$ 可能不是质数（$2\le M\le {10}^9$），不能求乘法逆元。所以用 前后缀积 来剔除某一个孩子：把每个邻居的分支因子排成一个数组，用前缀积 × 后缀积得到「去掉第 $i$ 个因子」的乘积，从而计算每个孩子的 $\text{up}$。

复杂度

• 时间：$O(N)$（两次遍历 + 每个节点一次前后缀积）
• 空间：$O(N)$

学到

• 换根 DP 的经典套路：第一遍自底向上求子树答案，第二遍自顶向下利用「兄弟/父侧」信息求全树答案。
• 当模数不保证是质数时，用前后缀积代替除法，或者用「根」的等价技巧避免求逆元。
• 黑色集合「连通且包含中心」转化成分支乘积 $\prod (\text{sub}+1)$ 的思想。