主要思路
如果你正确理解了题意，那么就不难想到用\(O(n)\)的 DFS 求出每一个叶子结点的上下界（然后我就没想了）。二分区间上的两个端点来获得总长度即可。
树上启发式合并 | DSU on tree
简述
树的结构让某些数据难以直接快速合并，所以就有了树上启发式合并，一种把合并时间为\(O(n)\)优化成\(O(\log n)\)的神奇方式。如果您先前学习过树链剖分，那么学习树上启发式合并就非常简单了。
Codeforces 1239A:Ivan the Fool and the Probability Theory 题解
主要思路
首先需要知道一个性质：如果第一行和第一列确定，那么这个方案就已经完全确定了。这个可以用归纳法证明：
证明 如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定，那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定，那么根据上述描述，便可生成一个唯一的方案。
所以欲记录方案的个数，那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。
设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然，可以自行推导（确实啊）。
最后答案就是把所有情况加起来，再减去非法的两种情况（也就是左上角的三格同色的情况）。
「杂题集」- 2019年10月16日
Codeforces 1174D:Ehab and the Expected XOR Problem 题解
主要思路
这道题还蛮妙的，自己比较顺利的思考出来了。
考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：
- 不存在两个相同的前缀和。
- 不存在一对前缀和，其异或值为\(x\)。
针对\(x\)的大小关系，我们可以分成两种情况：
- \(x \geq 2^n\)，不存在一对\((S_i, S_j)\)的异或为\(x\)，因为存在更高的位并不会被消除。
- \(x < 2^n\)，我们发现每选择一个数作为前缀和，整个\(2^n\)中就会少一个对应的可以被选择的数。所以，我们每次选一个作为\(S_i\)的数时，都要把\(S_i xor \ x\)打标记。
结合一下就可以了。
「NOIp 2012 疫情控制」题解
主要思路
大概可以想到二分出时间，然后把所有的点往上跳，再把能跨子树分配的点进行分配。思路差不多就是这样，还是很自然的一个思路。
但是有一些细节值得注意：跨子树分配和当前子树覆盖的优先级需要处理好。如果这个不处理好只能拿到洛谷上 80% 的数据。这个地方我改了很久，最后发现需要把跨子树分配作为第一枚举，然后再在枚举之间二次枚举子树覆盖需求（放在堆里，贪心配对即可）。