树上启发式合并

对于如下的一些问题，树链剖分、树上差分等常见手段就不是很好应对了：

• 询问树的每个子树内有多少种颜色
• 询问树的每个子树内出现至少 k 次的颜色有多少种
• 询问树上最长的路径，该路径上每个颜色的节点出现了偶数次
• 询问树的每个子树内某个深度的节点有多少个
• 询问树的每个子树内出现次数最多的颜色出现的位置编号的和
• 略略略

以上问题主要从 zyf2000 的博客内总结得来，且全部是 CF 上出现的题目。全部可以用树上启发式合并轻松解决。

所以什么是树上启发式合并？

大家可以先自己总结一下上面的 6 个问题有什么共同点，以及在利用常见算法解决它们的时候是否遇到了什么相似的困难。这样可以更清楚地理解我们为什么需要树上启发式合并。

适用范围

树上启发式合并是一种基于轻重链剖分的增量法算法。使用它需要有几个先决条件：

• 答案可以分解为若干贡献，且对答案的贡献需要在每个节点处统计，只与子树有关。
• 可以在 $O(n)$以下的时间内完成贡献的单次增量，或者单次减少。

第一个条件意味着如果答案不可分解，我们是不能使用树上启发式合并的。这个条件与树的点分治类似。

第二个条件意味着如果单次增量过于困难，我们不如直接暴力。如果答案可以合并，我们不如使用数据结构直接维护，而不需要使用树上启发式合并。

当两个条件同时满足时，我们可以考虑使用树上启发式合并 (但是是否一定可以，我不确定)。

算法流程

以” 统计每个节点的子树内颜色个数” 为例子，我们来熟悉以下流程。

• 目标：获得子树 $x$的答案
• 递归获得所有轻儿子的答案
• 清空每个轻儿子的子树内的贡献
• 递归获得重儿子的答案
• 递归累加所有轻儿子的子树内的贡献
• 累加节点 $x$的贡献
• 获得子树 $x$的答案

而在流程中 “累加节点 $x$的贡献” 可以用一个桶来维护，将每个节点丢到对应颜色的桶中，动态维护有多少个桶非空。

这样的复杂度是 $O(n\log n)$的，并且已经可以解决一开始提到的所有问题。不难发现那些问题与这个例子的唯一不同就是用来维护贡献的数据结构不同。

复杂度分析

这个算法的时间复杂度是 $O(n\log n)$的 (不考虑数据结构的复杂度)。

如果没有 “递归清空所有轻儿子的子树内的贡献”，和 “递归累加所有轻儿子的字数内的贡献” 这两个操作，复杂度将会是 $O(n)$的，但是多了这个操作，似乎有可能退化成 $O(n^2)$。实际上不会，因为对于节点对 $(x,y)$如果 $x$递归清空轻儿子的贡献时会访问到 $y$，意味着 $y$不在 $x$的重儿子的子树内，也就是说 $y$向根走时，遇到的每一条轻边的上面节点都会清空 $y$，反之不会清空 $y$。我们有知道对于任意节点，它头上的轻边条数是 $O(\log n)$级别的，因此总复杂度就是 $O(n\log n)$。

实例代码

附上 CodeForces375D Tree and Queries 的代码。这道题有 $m$次询问，每次询问子树 $x_i$内出现次数多于 $k_i$的颜色的个数。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define MX 100005

using namespace std;

template <typename T> void read(T& x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
}

struct FEN
{
    int sum[MX];

    void add(int p, int x)
    {
        if(!p) return;
        for(int i=p; i<MX; i+=i&-i)
            sum[i] += x;
    }

    int qur(int p)
    {
        if(!p) return 0;
        int x  =0;
        for(int i=p; i; i-=i&-i)
            x += sum[i];
        return x;
    }
} F;

int n, m;
int col[MX], fst[MX], nxt[MX*2], v[MX*2], lnum;
int siz[MX], son[MX], num[MX], ans[MX];
vector<pair<int, int> > qur[MX];
int tot;

void addeg(int nu, int nv)
{
    nxt[++lnum] = fst[nu];
    fst[nu] = lnum;
    v[lnum] = nv;
}

void input()
{
    int a, b;
    read(n); read(m);
    for(int i=1; i<=n; i++) read(col[i]);
    for(int i=1; i<n; i++)
    {
        read(a); read(b);
        addeg(a, b);
        addeg(b, a);
    }
    for(int i=1; i<=m; i++)
    {
        read(a); read(b);
        qur[a].push_back(make_pair(b, i));
    }
}

void pre_dfs(int x, int f)      //轻重链剖分
{
    siz[x] = 1;
    for(int i=fst[x]; i; i=nxt[i])
        if(v[i] != f)
        {
            pre_dfs(v[i], x);
            siz[x] += siz[v[i]];
            if(siz[v[i]] > siz[son[x]])
                son[x] = v[i];
        }
}

void modify(int x, int f, int t)//用于清空或累加一棵子树的贡献
{
    for(int i=fst[x]; i; i=nxt[i])
        if(v[i] != f)
            modify(v[i], x, t);
    F.add(num[col[x]], -1);
    num[col[x]] += t;
    F.add(num[col[x]], +1);
}

void dfs(int x, int f)
{
    for(int i=fst[x]; i; i=nxt[i])
        if(v[i]!=f && v[i]!=son[x])
            dfs(v[i], x), modify(v[i], x, -1);
    if(son[x]) dfs(son[x], x);
    for(int i=fst[x]; i; i=nxt[i])
        if(v[i]!=f && v[i]!=son[x])
            modify(v[i], x, +1);
    F.add(num[col[x]], -1);
    num[col[x]]++;
    F.add(num[col[x]], +1);
    for(auto it=qur[x].begin(); it!=qur[x].end(); it++)
        ans[it->second] = F.qur(MX-1) - F.qur(it->first-1);
}

int main()
{
    input();
    pre_dfs(1, 0);
    dfs(1, 0);
    for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
    return 0;
}