NOI 一轮复习：简单树形问题

树链剖分

每次跳重链即可完成树上 K 级祖先问题，而且通常比长链剖分快。

树上启发式合并

本质上是枚举每个节点时，直接枚举子树来计算答案的一种暴力。但是由启发式合并，我们可以最后枚举重儿子的信息，然后直接保留，这样就可以在统计父亲答案时不再重新枚举重儿子的信息。

void dfs(int x, bool keep) {
    for (int y : T1.G[x]) if (y != T1.fa[x] && y != T1.son[x]) dfs(y, 0);
    if (T1.son[x]) dfs(T1.son[x], 1);

    for (int y : T1.G[x]) if (y != T1.fa[x] && y != T1.son[x]) {
        for (int i = T1.dfn[y]; i <= T1.dfn[y] + T1.sz[y] - 1; ++i) {
            ...
        }
        for (int i = T1.dfn[y]; i <= T1.dfn[y] + T1.sz[y] - 1; ++i)
            add(T2.dfn[T1.idx[i]], 1);
    }

    add(T2.dfn[x], 1);

    if (!keep) {
        for (int i = T1.dfn[x]; i <= T1.dfn[x] + T1.sz[x] - 1; ++i)
            add(T2.dfn[T1.idx[i]], -1);
    }
}

例题

[北京市赛 2025] 最近公共祖先

Portal.

LCA 问题显然考虑枚举 LCA 是什么，于是在第一棵树上启发式。当枚举到一个新的节点时，如果它在第二棵树上是 LCA 的儿子，那么要统计此时第二棵树上 LCA 的子树中被“激活”了多少个节点，减去枚举节点所对应的小子树内的被激活的节点。代码。

[Nanjing Regional 2025] Cyan White Tree

Portal.

需要在 LCA 处统计信息不难考虑启发式合并。强制令 $c\ge w$ ，那么只需要在线段树上查询一个后缀最大值即可。

唯一的问题是在保留重儿子信息时，需要将其加上当前节点的信息。也就是说，区间修改然后平移。但是是全部平移，因此直接在线段树上打 tag 然后记一个偏移量 delta 即可。代码。