Problem D – Codeforces Round #127 (Div. 1)
多模式串匹配，是不是又是AC自动机啊？
显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到$\mathrm{O}(K)$，K为文本串总长（虽然单个字符串的长度极小可以$\mathrm{O}(NK)暴跳$）。这样就构建出一个由$1$到$n$构建的数列。
枚举$15!$的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数$x$，只要知晓当前的排列中前$j$位分别是哪些数，就可以立刻算出$x$加入排列后新增的逆序对数量。则我们考虑状压DP。 （更多…）
（2022.11.21 重写）
设 $\newcommand\siz{\operatorname{siz}}\newcommand\hson{\operatorname{hson}}\siz(x)$ 表示 $x$ 的子树大小（含 $x$），$\hson(x)$ 表示 $x$ 的重儿子。将边 $(x,\hson(x))$ 称为一条重边，其余不满足该条件的边称为轻边；将相邻的重边两两相连形成的链称为重链。
一棵以 $\newcommand\rt{\text{rt}}\rt$ 为根的树，其重心 $c$ 满足以下条件：
- $c$ 在以 $\rt$ 为顶的重链上；$(1)$
- $c$ 的所有祖先（记其中一个为 $x$），均满足 $\siz(\hson(x))>\frac{\siz(rt)}{2}$；$(2)$
- $\siz(\hson(c))\leq \frac{\siz(rt)}{2}$。$(3)$