题解：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 的贡献是独立的，线段树维护即可。