学校信竟换了新老师，第一节课就让我知道了原来还有这个算法。

引入

第一次听到启发式合并，是在并查集中，也叫按秩合并，就是将小的树接到大的树上以减少修改量，单开按秩合并可以优化到 $O(\log n)$，证明同重链剖分。加上路径压缩可以优化到 $O(α(n))$，接近 $O(1)$。
我理解的启发式就是找一个感觉会更优的方法来优化，实际上是很严谨的。

简介

那类似的，我们能不能在树上搜索的时候用启发式合并呢？有的兄弟，有的。
树上启发式合并，又称 DSU on tree （可 DSU 不是并查集吗？），是⼀种相当暴力的算法，可以用来解决很多树上计数问题。

原理

重链剖分中已经讲过重儿子的相关概念了。我们可以仿照并查集，将轻儿子的结果合并到子树最大的儿子，即重儿子上。这样类似重链剖分，就从 $O(n^2)$ 优化到 $O(n\log n)$ 了。

实现

具体的：

    1. 先遍历轻儿子，预处理出来但不计算贡献。
    1. 再遍历重儿子，加上它的贡献（然后加上自己本身的贡献，看题目）
    1. 最后加上轻儿子的贡献

实际上，就是把轻儿子的结果加到重儿子上，可搭配数据结构。

模板

使用了 DFS 序，更方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int n,dfn[N],seq[N],tot,sz[N],w[N];
void pdfs(int u,int fa){//预处理喵 
    dfn[u]=++tot,seq[tot]=u,sz[u]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        pdfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[w[u]]) w[u]=v;
    } 
}
void add(int u){
    //添加贡献
}
void clear(){
    //清空贡献
}
void dfs(int u,int fa,bool save){//save表示是否要保留贡献（即是否为重儿子）
    for(int v:g[u]){
        if(v==fa||v==w[u]) continue;
        dfs(v,u,0);
    }
    if(w[u]) dfs(w[u],u,1);
    add(u);
    for(int v:g[u]){
        if(v==fa||v==w[u]) continue;
        for(int i=dfn[v];i<dfn[v]+sz[v];i++) add(seq[i]);
    }
    ans[u]=/*喵*/;
    if(!save) clear();
}

例题

CF600E Lomsat gelral

上来就紫题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e9;
int n,c[N],dfn[N],seq[N],tot,sz[N],w[N];
vector<int> g[N];
void pdfs(int u,int fa){//预处理喵 
    dfn[u]=++tot,seq[tot]=u,sz[u]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        pdfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[w[u]]) w[u]=v;
    } 
}
int cnt[N],ans[N],mx;
vector<int> tmp;
void add(int c){
    cnt[c]++;
    if(cnt[c]>mx) tot=c,mx=cnt[c];
    else if(cnt[c]==mx) tot+=c;
    tmp.push_back(c);
}
void clear(){
    for(int c:tmp) cnt[c]=0;
    tot=0;mx=0;tmp.clear();
}
void dfs(int u,int fa,bool save){
    for(int v:g[u]){
        if(v==fa||v==w[u]) continue;
        dfs(v,u,0);
    }
    if(w[u]) dfs(w[u],u,1);
    add(c[u]);
    for(int v:g[u]){
        if(v==fa||v==w[u]) continue;
        for(int i=dfn[v];i<dfn[v]+sz[v];i++) add(c[seq[i]]);
    }
    ans[u]=tot;
    if(!save) clear();
} 
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    pdfs(1,0);tot=0;
    dfs(1,0,1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}