这是本文档旧的修订版！
错题集 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,i-1),S(l,i)$ 具有高度相似性，于是考虑使用可持久化线段树维护。
线段树的每个版本 $i$ 维护所有 $S(l,i)(1\le l\le i)$ 的答案，而版本 $i$ 只需要在版本 $i-1$ 的基础上稍微修改即可。
线段树相邻版本的差异来自 $F(l,i)(1\le l\le i)$，$F(l,i)(1\le l\le i)$ 至多有 $O(\log v)$ 个取值，考虑依次插入线段树。
而又有 $S(l,i)\subset S(l-1,i)$，于是考虑差分维护 $S(l,i)(1\le l\le i)$，令 $S(l,i)=\sum_{j=l}^i d_{j,i}$。
对所有相同的值 $v$，设该值最后一次出现位置为 $last$，于是有 $1 \le l\le last,v\in S(l,i)$。
于是对所有不同的值，考虑维护每个值对 $d_{last,i}$ 的贡献即可，时空间复杂度 $O(n\log n\log v)$。
