| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ? | 9 | Ø | Ø | Ø | O | . | O | . | Ø | O | O | O | . |
A
UpSolved by Henry.
极角排序。
B
UpSolved by XLor.
对 $A$ 集合的限制条件进行补集转化，则其价值等于 $|A| \choose 2$ 减去每个点的权值小于等于其自身的祖先个数。
假设每个点权值不同，考虑将 $B$ 集合一个放入 $A$ 集合的贡献，可以注意到要减去祖先和子树内来自 $B$ 集合本身的点的贡献，加上（实际为减去）祖先和子树内来自 $A$ 集合的贡献，这两部分合并起来等价于考虑了子树和祖先所有点，因此每个点从 $B$ 集合移到 $A$ 集合的贡献是一个常数，排序后贪心选取即可。
考虑存在相同权值的点对情况，容易证明深度小的点一定相对于大的点先选，并且先选浅的点能带来更多贡献，因此在转移贡献上多减去该点祖先上和该点权值相同的点个数，一起排序即可。
C
UpSolved by XLor.
简化问题：求一个串的本质不同子序列。
考虑 $dp[i]$，最后一个选 $i$ 位置产生的本质不同子序列个数，答案为 $\sum_{i=1}^n dp[i]$。
记 $last[i]$ 表示 $i$ 之前最后一个与第 $i$ 位字母相同的位置，有转移方程：
$$
dp[i]=\sum_{j=last[i]}^{i-1} dp[j]
$$
子问题一：求一个串长度为 $len$ 本质不同子序列个数，$dp$ 时添加一维长度。
子问题二：两个子序列分别匹配到位置 $i$ 和 $j$ 时的方案数，且两个子序列长度相同且位置对应相同，类似于简化问题，只不过是维护两个最后位置，转移时选一个矩形框。
子问题三：两个子序列从位置 $i$ 和 $j$ 开始匹配的方案数，且两个子序列长度相同，类似于子问题二，转移时选一个矩形框。
回到原题，应用子问题一，得到第一个子序列长度严格大于第二个的方案数，应用子问题二三，用类似的二维矩形框的方式容斥掉前面相同的部分，乘上使用子问题三的后缀矩形框，得到两个子序列长度相同时的方案数。
D
Solved by Henry.
签到。
F
Solved by XLor.
仙人掌。
H
UpSolved by Forsaken.
I
Solved by Henry.
dp。
J
Solved by XLor.
KMP。
K
Solved by Henry。
一个结论：如果存在一个叶子结点有兄弟，则其必胜，因为若他的后继有必胜态，则其先手一定也可以转移到这个必胜态，因此只会留下必败态给后手玩家。
考虑每个叶子结点第一个非二度祖先或根节点的父亲，如果存在一个距离是奇数，则必胜，因为先手玩家可以控制链的奇偶性，否则必败。