题解：P8493 [IOI2022] 数字电路

令

s(u)

表示

u

的儿子的集合，

f_u

表示

u

子树内方案数，

g_u

表示要让

u

是

1

，

u

子树内方案数。特别地，对叶子节点

u

，

g_u = [u 被赋值为1]

。

那么

f_u = |s(u)|\prod_{v \in s(u)} f_v

。

求

g_u

可以枚举

s(u)

的子集

S

表示恰好

S

集合中的点是

1

。

\\=\sum_{S \subseteq s(u)} |S|\prod_{v \in S} g_v\sum_{T \subseteq s(u) - S}\prod_{v \in T} (-g_v)\prod_{v \in s(u) - S - T} f_v \\=\sum_{U \subseteq s(u)} \prod_{v \in s(u) - U} f_v \sum_{S \subseteq U} |S|\prod_{v \in S}g_v\prod_{v \in U - S} (-g_v) \\=\sum_{U \subseteq s(u)} \prod_{v \in s(u) - U} f_v \prod_{v \in U} g_v \sum_{S \subseteq U} |S|(-1) ^ {|U| - |S|} \\=\sum_{U \subseteq s(u)} \prod_{v \in s(u) - U} f_v \prod_{v \in U} g_v[|U|=1] \\=\sum_{v \in s(u)} g_v \prod_{w \in s(u) - \{v\}} f_w$$ 剩余部分和其余题解一样，发现每个节点 $g_u$ 对 $g_1$ 的贡献是独立的，线段树维护即可。

文章操作