这是一个高中的时候从来没有学会的东西。但是现在想想实在是非常的简单。

    我们考察这样一个动机：很多时候我们想要做一些子树上的问题，想要对每一个点计算出它对应的某一个值，而这个值是由它的子树里的点决定的。这个时候我们天然地想到 dfs ，但是它有一个问题。当我们递归到某一个点 x 的时候，我们考虑它的某两个儿子 u 和 v 。假如我们向下走到 u 然后进行一些计算，最后不还原这些计算的话，计算 v 的时候就会出问题。假如我们还原的话，我们最后再算 x 的值的时候需要重新走一遍 u 。

    我们怎么才能让这样的重复不影响到我们的效率呢？很自然的，我们希望最大的儿子不要重复就行。

    就是这样的自然的思路，所以它才是“启发式”的。怎么证明它的正确性呢？

    我们考虑轻重边的定义，重边就是连接重儿子的边，而 u 的重儿子 v 就是 v 的子树大小比 u 的子树大小一半还大的儿子。轻的定义同理。一个点可以没有重儿子。

    我们每次都让重儿子不要重复。为什么这样是对的呢？因为轻边在从根到任意一个点的链上不会超过 logn 条。因为每次大小至少砍一半，所以不能太多。我们每个点只会因为祖宗被一个轻边连所以才重复，现在轻边数量最多 logn ，那么复杂度也就 nlogn 了。

    最后，我们需要注意一点，重复某一个点并不是说第一次遍历和后一次重复必须是相同类型的操作。实际上完全可以不一样。