[ARC197D] Ancestor Relation 题解

好题啊好题。记 表示矩阵的第 行的内容（用 bitset 维护）。

考虑什么时候有 。因为与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。所以有 或 ，前者对应 是 的祖先，后者则对应 是 的祖先。容易证明这是一个充要条件，那么若 ，则一定不存在 与 。

接下来考虑一种特殊情况：，此时 在一条没有任何分岔的一条“链”上，那么这条链上的节点的位置就可以互换。设一组 相同的点的数量为 ，那么这一组点可以带来 的贡献。

此外，，显然需要有 。那么我们就总结出以下三条条件或贡献：

• 。
• 或 ，当且仅当 。（等价于：，当且仅当 或 。）
• 对于极多的 个 相同的数，可以带来 的贡献。

于是按以上三点计算即可。时间复杂度 。

提交记录。