题解：AT_agc079_a [AGC079A] Tree Contraction Sequence

· · 题解

对于所有满足 2\le u\le n 的 u，令 v 为不在 u 子树中的所有编号大于 u 的点中编号最小的点。若 v 存在，则必然地，u 必须早于 v 操作。因为树的连边方式保证父节点的编号一定小于儿子节点的编号，而 v 不在 u 的子树且 v>u，所以 v 不为 u 的祖先，u 也不为 v 的祖先。如果先操作 v，则 fa_v 的序列将变得不连续，一定不合法。

那么怎么找所有这样的偏序关系 u<v 呢？考虑将节点编号作为下标建立线段树，对每个区间维护 dfn 的最小值和最大值。对于 u，就可以二分找到第一个 \max_{dfn}>dfn_u+siz_u-1 点或第一个 \min_{dfn}<dfn_u 的点。由于我不会高级算法，这部分我是 O(N\log^2N) 的。就是每二分一次调用一次 Query。

我们已经找到了所有这样的偏序关系 u<v，把 v 作为 u 的父亲建立新的树（森林）。记 siz_u 表示在新树（森林）中 u 的子树大小（包含 u），则答案为：

ans=\frac{(n-1)!}{\prod\limits_{i=2}^{n}siz_i} [Code](https://atcoder.jp/contests/agc079/submissions/80714493)。