题解：AT_arc197_d [ARC197D] Ancestor Relation

记 $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})$。