ARC121F

解法

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)

。

文章操作

相关推荐

评论

ARC121F