1路径压缩
压缩后查一次大概多快？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2按秩合并
不按秩合并可能出现什么？
3Kruskal 算法
遇到两端已连通的边为什么要跳过？
4Prim 算法
Kruskal 和 Prim 各适合什么图？
5最小生成树练习
动手写 Kruskal 版本。
6并查集的其它用途
判断加边后图是否成环，怎么用并查集？
7树的性质
给一张 n 个点 n-1 条边的连通图，它一定是树吗？
8树的直径
为什么两次搜索就够？
9树的重心
一条链的重心在哪？
10树形 DP 入门
这和普通 DP 有什么不同？
第 1 页 · 背面（答案）
参考答案（家长）：可能连成一条长链，查祖先变慢。
参考答案（家长）：几乎是常数时间。
参考答案（家长）：Kruskal 适合稀疏图，Prim 适合稠密图。
参考答案（家长）：选了会成环，违反树的定义。
参考答案（家长）：加边前若两端已同组，说明会成环。
参考答案（家长）：排序加并查集，二十行左右。
参考答案（家长）：可以证明第一次找到的最远点一定是直径的一个端点。
参考答案（家长）：一定是。
参考答案（家长）：状态转移沿着树的结构走，通常用递归实现。
参考答案（家长）：正中间那个点。
第 2 页 · 正面（题目）
11树形 DP：选或不选
状态该怎么定？
12树形 DP：转移
写出这两条转移。
13树上前缀和
这和数组前缀和的思路一样吗？
14最近公共祖先
树上两点距离怎么用它算？
15倍增求祖先
跳 13 步怎么拆？
16倍增求公共祖先
为什么跳到"不相遇"而不是"相遇"？
17图论建模
倒水问题怎么建模成图？
18状态图搜索
八数码的状态是什么？
19状态判重
为什么必须判重？
20双向广搜
为什么双向能快？
第 2 页 · 背面（答案）
参考答案（家长）：选它等于自身价值加所有孩子的"不选"；不选它等于所有孩子取较大值之和。
参考答案（家长）：定两个状态：这个点选和不选时子树的最优值。
参考答案（家长）：两点到根的深度之和，减去两倍的公共祖先深度。
参考答案（家长）：一样，只是"前一个"换成了"父节点"。
参考答案（家长）：相遇的可能是更高的祖先，取最后不相遇的再上一层才最近。
参考答案（家长）：8 加 4 加 1，三次跳完。
参考答案（家长）：九个格子当前的数字排布。
参考答案（家长）：每种水量组合是一个点，一次倒水操作是一条边。
参考答案（家长）：两个小的搜索树之和，远小于一个大的搜索树。
参考答案（家长）：否则会重复搜索同一状态，量级爆炸。
第 3 页 · 正面（题目）
21优先队列广搜
这说明什么？
22图论练习一
动手完成。
23图论练习二
这是什么算法？
24图论练习三
Kruskal 和 Prim 都试一遍。
25图论练习四
该用哪个算法？
26图论小结
给每样写一句适用场景。
27高级数据结构：堆
堆和排好序的数组比，优势在哪？
28堆的结构
小根堆的堆顶是什么？
29堆的上浮与下沉
为什么这两个操作是 log 级？
30堆的应用
求一百万个数里最大的十个，怎么用堆？
第 3 页 · 背面（答案）
参考答案（家长）：遍历所有点，未访问就搜一遍并计数。
参考答案（家长）：Dijkstra 本质是带优先级的广搜。
参考答案（家长）：结果应该一样，写法不同。
参考答案（家长）：拓扑排序。
参考答案（家长）：能说清适用场景，遇到题才知道该用哪个。
参考答案（家长）：Bellman-Ford 或它的队列优化版，不能用 Dijkstra。
参考答案（家长）：最小的元素。
参考答案（家长）：插入新元素时不用重新排序，只要 log 级调整。
参考答案（家长）：维护一个大小为 10 的小根堆，比堆顶大就替换。
参考答案（家长）：树高是 log n，最多换这么多层。