这是本文档旧的修订版！
目录
错题集 2
1、Ancient Distance
题意
给一个有根树，在树上选择 $k$ 个关键点(根必须选)，使得所有点到最近关键祖先(可以是自己)距离的最大值最小。
求出 $k$ 分别为 $1\sim n$ 时答案的和。
题解
考虑贪心，假设已知最小距离为 $d$，发现每次取树中深度最大的点的 $d$ 级祖先作为关键点最佳。
而选取该节点作为关键点后可以直接删去该关键点的子树，然后继续从新的树中选择深度最大的点。
考虑用树链剖分和线段树维护每个点的 $d$ 级祖先和子树删除操作。
另一方面，发现如果将最小距离设为 $d$，则每次子树删除操作至少删去 $d$ 的节点，于是操作次数为 $O(\frac nd)$。
考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。
总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$，于是总时间复杂度为 $O\left(n\log^2 n\right)$。
注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
2、Greetings Souvenir
题意
给定一棵大小为n的树，且树上的每个节点有一个权值 $a_i$，现在要给每个节点确定一个数值 $b_i$。
定义 $val_i=b_i\ast$( $i$ 子树内有多少个点的权值 $a_i$ 等于 $b_i$)，要求所有点 $val_i$ 的 $mex$ 尽可能大。
题解
乱搞题，首先考虑每个 $a$，假如有 $c_i$ 个节点权值为 $a$，对所有 $b_i=a$ 的点，其 $val_i$ 的可能取值只有 $a,2a\cdots c_ia$ 共 $c_i$ 个。
于是所有可能的取值只有 $\sum_{i=1}^n c_i=n$ 个。
在每个点 $i$ 与其可能取值的 $val_i$ 间连一条边，时空间复杂度 $O(n^2)$。为防止爆空间，本题用 $\text{bitset}$ 存边。
最后考虑进行二分图匹配，从小到大给所有可能值匹配，如果匹配失败则立即结束，时间复杂度 $O(n^3)$。
考虑乱搞，强行对匈牙利算法使用当前弧优化，于是时间复杂度降为 $O(n^2)$。
3、Interval
题意
给定序列 $a_1,a_2\cdots a_n$，定义函数 $F(l,r)=a_l\text{&} a_{l+1}\text{&} \cdots a_r$，定义不可重集 $S(l,r)=\{l\le a\le b\le r,F(a,b)\}$。
接下来若干询问，每次询问 $|S(l,r)|$，强制在线。
题解 1
首先，对固定的 $r$，易知 $F(l,r)$ 至多有 $O(\log v)$ 个取值，因为 $F(l,r)-F(l-1,r)=0$ 或 $F(l,r)$ 中的某个不为 $0$ 的位。
线段树可以 $O(\log n)$ 快速计算 $F(l,r)$。考虑对 $l$ 二分，可以 $O(\log n\log v)$ 得到对固定的 $r$，$F(l,r)$ 的所有可能取值。
接下来考虑维护答案，发现 $S(l,r-1),S(l,r)$ 具有高度相似性，于是考虑使用可持久化线段树维护。
线段树的每个版本 $r$ 维护所有 $S(l,r)(1\le l\le r)$ 的答案，而版本 $r$ 只需要在版本 $r-1$ 的基础上稍微修改即可。
线段树相邻版本的差异来自 $F(l,r)(1\le l\le r)$，$F(l,r)(1\le l\le r)$ 至多有 $O(\log v)$ 个取值，考虑依次插入线段树。
而又有 $S(l,r)\subset S(l-1,r)$，于是考虑差分维护 $|S(l,r)|(1\le l\le r)$，令 $|S(l,r)|=\sum_{i=l}^r d_{i,r}$。
对所有具有相同的值 $v$ 的 $F(a,b)(b\le r)$，设 $\text{last}=\max(a)$，于是有 $1 \le l\le \text{last},v\in S(l,r)$。
于是对所有不同的值，考虑维护每个值对 $d_{\text{last},r}$ 的贡献即可，时空间复杂度 $O(n\log n\log v)$。
题解 2
对固定的 $r$，考虑枚举过程中维护 $a_1\sim a_{r-1}$ 中数位为 $0$ 的最后位置 $a_\text{last}$。
如果 $a_r$ 某数位为 $0$，则该数位对应的 $\text{last}$ 必有 $F(\text{last}+1,r)\neq F(\text{last},r)$。
于是可以 $O(\log v)$ 时间求出所有 $F(l,r)(1\le l\le r)$ 的可能取值。
而对于可持久化线段树的维护，可以改用区间标记永久化维护 $F$ 带来的影响。
4、Ancient Distance
题意
给定排列 $p$，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价。
要求将 $p$ 转化为 $1,2\cdots n$，求最优策略下最小代价的期望。
题解
将 $p$ 转化为 $1,2\cdots n$ 等价于该置换只存在长度为 $1$ 的循环。
有引理 $1$：随机打乱一个长度为 $n$ 的循环，则循环的每个元素将等概率出现在长度为 $1\sim n$ 的循环中。
引理 $2$：每次选择一个完整的循环将其全部打乱一定是最佳选择。
设将一个长度为 $n$ 的循环打乱成 $n$ 长度为 $1$ 的循环的最小期望代价为 $f(n)$。
单独考虑每个点的期望代价，每个点在循环长度为 $i$ 的代价由 $i$ 个点均摊。
最后总代价为单个点代价的 $n$ 倍，得到$f(n)=n\sum_{i=1}^n \frac{\frac {f(i)}{i}}n+n=\sum_{i=1}^n\frac {f(i)}i+n(n\gt 1)$。
转化，得到 $f(n)=\frac {n(f(n-1)+1)}{n-1}(n\gt 2)$，边界条件 $f(2)=4,f(1)=0$。
