ARC121F Logical Operations on Tree

题意 ： 给定一棵树，现在需要为每一个点填写权值 ，每条边填写运算 。

填写完后，每次可以选择一条边 收缩，收缩产生的新点权值为 。（其中 是运算）

对于所有 种填写方案，求满足“存在一种收缩顺序使得最终剩余的点权值为 ”的方案数。

，时限。

---

先考虑给定填写情况，如何判定是否存在一种收缩顺序，使得最终剩余的点权值为 。

考虑一个叶子：（经典的去叶子归纳法）

• 若父边是 ，权值是 ，则必有解。

• 若父边是 ，权值是 ，对答案无影响，直接去掉。

• 若父边是 ，权值是 ，则先处理其余部分，最后收缩。

• 若父边是 ，权值是 ，则必定会将父亲置 一次，不妨首先收缩，这样危害最小。

按照这个策略从深往浅做就是，每个子树只会保留两条信息：最终权值，是否含 。

然后考虑 DP ：

记 表示 子树内 权值为 / 权值为 但不含 / 含 （且权值为 ） 的方案数。

当将子树 加入 时根据上述策略，能写出转移 ：

• 第一行 ： 。

• 第二行 ： 。

• 第三行 ： 任意一侧有 ，与 。

复杂度 。