[ARC121F] Logical Operations on Tree

· · 题解

一道比较简单的 ARC F。

题目链接

https://atcoder.jp/contests/arc121/tasks/arc121_f

题解

看到计算合法的方案数，套路地先考虑如何判断一个方案是否合法。

在列举了大量情况后，能够发现先操作所有 \text{AND} 边，后操作所有 \text{OR} 边，一定是不劣的。

形式化地，一个方案合法的条件，当且仅当将所有 \text{OR} 边断开后，形成的若干个连通块中至少有一个联通块的点权是全 1 的。

充分性

显然，如果有一个联通块的点权全 1，那么将所有联通块缩成一个点后，至少有一个点的点权为 1，并且图中只剩下 \text{OR} 边，显然合法。

必要性

只需要证明当所有连通块中都至少有一个 0 时，不存在一种边的操作顺序能使得最终剩下的点权为 1。

显然地，操作一次 \text{AND} 操作，并不能将一个连通块变成全 1 连通块。

并且，如果操作 \text{OR} 操作将两个联通块合并成一个连通块，则新连通块一定不是全 1 连通块。

证明：如果 \text{OR} 边的两个端点都是 0，则操作后的新点点权为 0；如果至少一个端点为 1，因为两个连通块都不是全 1 连通块，所以在其所在的连通块内仍至少存在一个 0，新连通块也不是全 1 连通块。

所以不管怎么操作，最终只能得到一个点权为 0 的点。

树形 \text{dp}

有了上述结论，我们统计方案数，本质上就是枚举 \text{OR} 边，将整棵树断成若干个连通块，然后在连通块内赋上点权，并且保证至少有一个全 1 连通块。

首先至少一个全 1 连通块不是很好做，考虑容斥，计算所有连通块都不是全 1 连通块的方案数。

这是一个经典的树形 \text{dp}：

设 f_{u, 0/1} 表示在以 u 为根的子树内划分连通块，u 点所在的连通块内，0 表示已经有点权为 0 的点了，1 表示还没有点权为 0 的点。

转移就考虑枚举每一条边 (u, v) 是否断开（v 为 u 的儿子节点）。

2 \cdot f_{u, 0} \times f_{v, 0} + f_{u, 1} \times f_{v, 0} + f_{u, 0} \times f_{v, 1} \longrightarrow f_{u, 0} f_{u, 1} \times f_{v, 1} + f_{u, 1} \times f_{v, 0} \longrightarrow f_{u, 1}

注意：当 v 所在联通块还没有点权为 0 的点时，(u, v) 是不能断开的，因为要求没有连通块是全 1 连通块。

最终答案为 2 ^ {2n - 1} - f_{1, 0}。

时间复杂度 \Theta(n)。

代码链接

https://atcoder.jp/contests/arc121/submissions/43276183