【置顶】嘴巴

要锻炼思维就不能每道都写。（然而这并不意味你写就草草写！xml 的赛场调试水平之差有目共睹 qaq…）因 此 开 了 「㗅」坑。

嘴巴题不会放在「学习计划」里。

因为是嘴巴题所以低配，一律 details。

加星号的是打算有时间写写的。

$CF741D$

「重排」这个条件非常强：所有字符只能有最多一种出现奇数次。奇偶性考虑异或。对于一种 01 路径维护最长的那条。启发式合并每个子树的路径。O(nlogn)

$BZOJ4771-$七彩树

多次询问子树 x 里深度为 [dep_x, dep_x + d] 有多少种不同的颜色。无脑线段树合并复杂度肯定错了嘛。 不考虑深度限制，初始时某颜色 c 的两个点 a、b 各自贡献是 1，到了 lca(a, b) 就要除去 1 个贡献。最后答案是子树和。 考虑深度限制：预处理距离每个 x <= 1 d 的答案。[dep_x, dep_x + d] 在 dfs 序上是连续的。 假设我们已经有 <="d" - 的答案，那就把深度为 的答案加进来，按 序插在主席树里就好。（好㗅 details>

$AGC051D$

巧妙处理。路径的分类标准是什么？我模糊感觉到不同的类别之间应该要有关联。怎么用合适的分类去把 abcd 关联起来呢？ 官方题解：分三类。 1. 过 $T$ 型。$S \rightarrow T \rightarrow U$, $U \rightarrow T \rightarrow S$ 2. 过 $V$ 型。$S \rightarrow V \rightarrow U$, $U \rightarrow V \rightarrow S$ 3. 回型。$S \rightarrow T \rightarrow S$, $S \rightarrow V \rightarrow S$, $U \rightarrow T \rightarrow U$, $U \rightarrow V \rightarrow U$ 枚举过 $T$ 型和过 $V$ 型的数量，列出一个好多组合数的柿子，然后变成阶乘再 FFT。。大概就完了，主要是分类比较神。

WC2018-即时战略

好像没什么特别妙的= =……？数据范围一眼 log。要一棵树支持：1. 加点 2. 快速跳到一个点 方法一：二分！LCT，在实链上不断二分，然后跳到下一个实链。 方法二：点分树 + 替罪羊重构。维护已知树的点分树，设 explore(x, y) = z，从 z 开始向上跳 logn 次找到 z 在 x 的哪个点分子树里，跳过去。这样的上跳要点分树深度次即 logn 次，于是是 O(nlog^2n) 的。