[ARC121F]Logical Operations on Tree

本文主要是介绍[ARC121F]Logical Operations on Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Logical Operations on Tree

题解

简单dp

首先我们很容易发现一种贪心的手段。
我们可以通过操作使树的一个叶子的值为$1$，并它连向其父亲的边是$or$，我们就将这个叶子保留到最后。
否则我们再枚举完这个点的子树后就向上操作一定是最优的。

• 当叶子为$1$，并且边是$or$时，如果我们保留下来最后再来$or1$，则最后剩下来的节点一定是$1$，我们会对其进行单独计算。
• 当叶子为$1$，并且边是$and$时，无论我们什么时候向上进行都不会对答案造成影响，还不如直接现在进行。
• 当叶子为$0$，并且边是$or$时，也不会对答案造成影响，也可以直接现在进行。
• 当叶子为$0$，并且边是$and$时，由于只有$or1$会使该节点的值改变为$1$，但$or1$我们是对其进行单独计算的，所以这个点的值为$1$时当且仅当它本来就是$1$，这个$and0$一定会对其造成影响，不如就现在进行。而这个点值为$0$时$and0$根本不会产生任何影响，不如就现在进行。

于是就可以证明我们的贪心做法是正确的，接下来可以用$dp$准确说并不是dp，只是一个计数对树的形态进行计算。

令$f_{x,0/1}$表示$x$节点的子树中不含$or1$，且它们全部操作完后得到的节点值为$0/1$的树的个数。
令$g_x$表示$x$的子树中含有 o r   1 or\,1

这篇关于[ARC121F]Logical Operations on Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---