树上启发式合并可以用于解决子树的问题，但是不可以带修改。

来看一道例题：

CodeForces600C

题意：

给出一棵树，每个结点有一种颜色，求每个结点的子树中出现次数最多的颜色，如果有多个出现次数最多的颜色，则将它们相加。

思路：

如果只是求子树的种类数的话似乎用dfs序+莫队也可以做？

考虑最暴力的$O(n^2)$做法，枚举每个点，暴力访问子树中的点，统计完以后将统计的num数组清空。

其实num数组清空是浪费的，因为对于它的父亲结点，也会用到它的子树的信息。

启发式就体现在这里，对于一个结点，让大的子树不清空，所以先树剖出它的重儿子，重儿子就保留子树上的信息。

所以步骤是这样的：

1.树剖出重儿子；

2.DFS遍历子树，先遍历轻儿子，再遍历重儿子；

3.如果当前根结点是重儿子，就不将信息清空，否则就清空。

时间复杂度为$O(nlogn*x)$，$x$为外部维护的时间。

时间复杂度的证明：

只有dfs到轻边时，才会将轻边的子树中合并到上一级的重链，树链剖分将一棵树分割成了不超过$logn$条重链。每一个节点最多向上合并$logn$次，单次修改复杂度$O(1)$。所以整体复杂度是$O(nlogn)$的。

代码：

struct edge
{
    int to;
    int next;
}eg[200010];
int val[100010];
int head[100010];
int top;
int par[100010],son[100010],tot[100010];
int num[100010];//颜色出现的次数
int cnt;//当前出现最多的颜色出现的次数
ll sum;//当前答案
ll ans[100010];
bool vis[100010];
void add(int x,int y)
{
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
int dfs1(int id,int fa)//处理出重儿子
{
    par[id]=fa;tot[id]=1;
    int maxson=-1;
    son[id]=0;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp==fa)continue;
        tot[id]+=dfs1(temp,id);
        if(tot[temp]>maxson)
        {
            son[id]=temp;
            maxson=tot[temp];
        }
    }
    return tot[id];
}
void calc(int id,int f)
{
    num[val[id]]+=f;
    if(f>0&&num[val[id]]==cnt)sum+=1ll*val[id];
    else if(f>0&&num[val[id]]>cnt)
    {
        cnt=num[val[id]];
        sum=1ll*val[id];
    }
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp!=par[id]&&!vis[temp])//重儿子不用访问，这里不用son[id]来判断的原因是轻儿子的重儿子仍然是要访问的
            calc(temp,f);
    }
}
void dfs2(int id,bool tp)//tp:是否是重儿子
{
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp!=par[id]&&temp!=son[id])
            dfs2(temp,false);
    }
    if(son[id])
    {
        dfs2(son[id],true);
        vis[son[id]]=true;
    }
    calc(id,1);ans[id]=sum;
    if(son[id])vis[son[id]]=false;
    if(!tp)
    {
        calc(id,-1);
        cnt=0;sum=0;
    }
}
int main()
{
    int n,x,y;
    scanf("%d",&n);
    top=0;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(1,0);
    sum=cnt=0;
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    printf("\n");
    return 0;
}