题解：AT_arc197_d [ARC197D] Ancestor Relation

wl2009 · 2025-05-08 10:16:32 · 题解

记 s_i = \sum_{j = 1} ^ n A_{i,j}，其中 n 为当前子树大小。每次找到除根外未被打上标记且 s_i 最大的 i，将其设为根的一个孩子。记 c = \sum_{j = 1} ^ n [A_i = A_j]，c 的具体含义为 i 所在的极大的链的链长。我们可以发现若 i 能成为根的孩子，则任意的满足 A_i = A_j 的 j 都能将 i 替掉，所以答案要乘上 c。将与 i 有祖先后代关系的点 j 打上标记，如果 j 已经被打上标记或者 A_j \subsetneq A_i，则说明答案为 0，因为一个点不可能有两个不存在祖先后代关系的祖先。然后递归进以 i 为根的子树即可。

还有一种更简洁的做法。我们枚举 i 和 j，若 A_i = A_j，则将 i 所在的点集 与 j 所在的点集合并，若 A_{i,j} = 1 且 A_i 和 A_j 之间不存在被包含关系，则答案为 0。最后答案即为每个点所在的集合大小的阶乘之积，原因同上文。将 A_i 由数组替换成 bitset 可以把时间复杂度从 O(n ^ 3) 降为 O(\frac{n ^ 3}{\omega})。