ARC121F

shiruoyu114514 · 2025-05-09 16:06:46 · 题解

解法 1：

考虑什么样的树合法。

断言：一棵树合法当且仅当在断掉所有 \operatorname{OR} 边后，至少有一个联通块没有 0。

证明：

充分性：直接把全 1 联通块缩在一起，并且操作除该联通块邻接 \operatorname{OR} 边外的所有边，然后再操作邻接边即可。

必要性：显然如果没有 \operatorname{OR} 边，不论怎么操作，联通块内都至少有一个 0，并且最后的运算结果为 0。

否则考虑第一次对 \operatorname{OR} 边操作时，由于边两端的联通块都至少有一个 0，而 \operatorname{OR} 至多会减少一个 0，所以操作后的联通块依旧至少有一个 0，转化为联通块个数 -1 的情况。

于是进行树形 DP 即可。

具体地，考虑容斥。令 dp_{i,0/1/2} 为在 i 子树内，i 为 0/i 子树内没有出过 0/i 子树内出过 0 的方案数。

当给 i 合并一个儿子时，如果 i 为 0，直接把贡献累加到 dp_{i,0} 上，否则除非当前状态为 dp_{i,1} 并且边为 \operatorname{AND} 并且儿子的对应状态为 dp_{j,2}，此时转移到 dp_{i,2}，否则原样转移即可。

时间复杂度 O(n)。

做法二：

考虑“剥叶子”状物。具体地，我们考虑当一个叶子以及其父子边的情况。

如果叶子为 \operatorname{OR} 0 或者 \operatorname{AND} 1，那么其对整个局势没有影响，可以直接剥掉。

如果为 \operatorname{OR} 1，那么直接赢了。

否则当对其进行操作的时候，无论何时，父亲会变成 0。最开始进行操作即可，因为如果父亲是 1，那么其所合并形成的最终节点一定为 0，最开始影响能小点。

于是可以 DP：令 dp_{i,0/1/2} 为 i 为 0/1 或者已经出现 \operatorname{OR} 1 的方案数。时间复杂度 O(n) 。