题解：AT_agc050_f [AGC050F] NAND Tree

SegTree · 2026-03-03 18:43:21 · 题解

该做法支持模数任意给定。

注意到 \text{NAND}(u,v)=1-uv，这可以用组合意义描述为，每次我们可以对于一个点集进行如下操作：

• 当点集大小 >1 时选择一条边：
• • 若染色为蓝边，答案乘以 -1，然后对两个点集分别染色问题。
• • 若染色为红边，终止该点集的染色。
• 否则将答案乘以 a_u。

那我们要对染色过程计算权值和，考虑删去所有蓝边，则每部分应该由一个点或者一条红边加上若干条未被染色的边。

那考虑染色顺序，相当于红边在它所在的部分一定是最后被染色的，并且比它周围的蓝边染色都要早。

那考虑对这个过程计数，设 f_{u,i} 表示以 u 为根的子树内，u 所在联通块中已经选择红边，且排名为 i 的权值，g_{u,i} 表示以 u 为根的子树内，未选择红边但给它预留的位置排名为 i，h_u 表示 u 所在联通块点集为 1 的权值和。

考虑转移，对于该边为红边/白边的情形可以直接枚举这条红边在两部分的排名；对于蓝边的情形，对该点为单点的情况转移也是简单的，对于转移 f/g 的情形需要另外枚举儿子所在联通块红边的排名，时间复杂度 O(n^3)，容易用前缀和优化到 O(n^2)。

代码：link。