树上启发式合并学习笔记

First Post:

Last Update:

Word Count:
2.4k

Read Time:
12 min

之前一直搞不懂 Dsu on tree，今天终于懂了，很激动，遂记录下来。

看到一篇博客，说：Dsu on tree=树上不删除莫队，然后就恍然大悟了。

我们回顾一下 Dsu on tree 的算法流程：

  1. 先遍历 的轻儿子，计算它们自己的答案，然后把贡献删去。
  2. 遍历 的重儿子，保留贡献。
  3. 再次遍历轻儿子，加入这些点的贡献，得到 的答案。

事实上跟不删除莫队还是不太一样的，但是都是有回滚的思想在里面的。

但感觉这东西不太厉害啊，能用这个的题基本都有一堆其他方法做。

且局限性比较大，需要满足：

  1. 只有查询
  2. 只和子树有关

而且复杂度也不一定优，唯一优点可能是小常数+好写？

把之前线段树合并的题单拿过来再做一遍（从这就已经能看出它的可替代性了）。

树上数颜色

本质上是区间数颜色，做法很多。

因为要练 Dsu，所以写了 Dsu。

确实感觉这东西和莫队差不多。

复杂度 。

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
58
59
60
61
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,m,now,son;
int a[maxn];
int head[maxn],buc[maxn],ans[maxn];
struct node{
    int siz,hson;
}t[maxn];
vector<int> g[maxn];
inline void dfs1(int u,int fa){
    t[u].siz=1;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
}
inline void add(int u,int fa){
    if(!buc[a[u]]) ++now;
    ++buc[a[u]];
    for(auto v:g[u]){
        if(v==fa||v==son) continue;
        add(v,u);
    }
}
inline void del(int u,int fa){
    --buc[a[u]];
    if(!buc[a[u]]) --now;
    for(auto v:g[u]){
        if(v==fa) continue;
        del(v,u);
    }
}
inline void dfs(int u,int fa,bool op){
    for(auto v:g[u]){
        if(v==fa||v==t[u].hson) continue;
        dfs(v,u,0);
    }
    if(t[u].hson) dfs(t[u].hson,u,1);
    son=t[u].hson;add(u,fa);
    ans[u]=now;
    if(!op) del(u,fa);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1,u,v;i<n;++i) cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
    for(re int i=1;i<=n;++i) cin>>a[i];
    dfs1(1,0),dfs(1,0,0);
    cin>>m;
    for(re int i=1,u;i<=m;++i) cin>>u,cout<<ans[u]<<'\n';
    return 0;	
}

[USACO17JAN] Promotion Counting P

本质上是二维数点，做法很多。

考虑 Dsu，逆序对用树状数组求一下即可。

复杂度 。

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
58
59
60
61
62
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,m,son;
int a[maxn],b[maxn];
int head[maxn],ans[maxn];
vector<int> g[maxn];
struct node{
    int siz,hson;
}t[maxn];
struct BIT{
    #define lb(x) (x&(-x))
    int tr[maxn];
    inline void add(int x,int val){while(x<=m) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
}A;
inline void dfs1(int u){
    t[u].siz=1;
    for(auto v:g[u]){
        dfs1(v);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
}
inline void add(int u){
    A.add(a[u],1);
    for(auto v:g[u]){
        if(v==son) continue;
        add(v);
    }
}
inline void del(int u){
    A.add(a[u],-1);
    for(auto v:g[u]) del(v);
}
inline void dfs(int u,bool op){
    for(auto v:g[u]){
        if(v==t[u].hson) continue;
        dfs(v,0);
    }
    if(t[u].hson) dfs(t[u].hson,1);
    son=t[u].hson;add(u);
    ans[u]=t[u].siz-A.query(a[u]);
    if(!op) del(u);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);m=unique(b+1,b+n+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(re int i=2,fa;i<=n;++i) cin>>fa,g[fa].push_back(i);
    dfs1(1),dfs(1,0);
    for(re int i=1;i<=n;++i) cout<<ans[i]<<'\n';
    return 0;	
}

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
58
59
60
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,m,sum,mx,son;
int a[maxn];
int head[maxn],buc[maxn],ans[maxn];
struct node{
    int siz,hson;
}t[maxn];
vector<int> g[maxn];
inline void dfs1(int u,int fa){
    t[u].siz=1;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
}
inline void add(int u,int fa){
    ++buc[a[u]];
    if(buc[a[u]]>mx) mx=buc[a[u]],sum=a[u];
    else if(buc[a[u]]==mx) sum+=a[u];
    for(auto v:g[u]){
        if(v==fa||v==son) continue;
        add(v,u);
    }
}
inline void del(int u,int fa){
    --buc[a[u]];
    for(auto v:g[u]){
        if(v==fa) continue;
        del(v,u);
    }
}
inline void dfs(int u,int fa,bool op){
    for(auto v:g[u]){
        if(v==fa||v==t[u].hson) continue;
        dfs(v,u,0);
    }
    if(t[u].hson) dfs(t[u].hson,u,1);
    son=t[u].hson;add(u,fa);
    ans[u]=sum;
    if(!op) del(u,fa),sum=mx=0;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,u,v;i<n;++i) cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
    dfs1(1,0),dfs(1,0,0);
    for(re int i=1;i<=n;++i) cout<<ans[i]<<' ';
    return 0;	
}

Blood Cousins

先跳到 级祖先上，那么问题变为：子树内颜色为 的点的个数。

相信大家都会写代码。

Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

又是 美好的每一天。

先处理出每个点到根的路径上每种字符出现次数的奇偶性，设为 。

点对 合法，当且仅当 至多有一个 。

设当前处理到点 ，显然以 为根的子树的答案分两部分：以 为 的路径和不以 为 的路径。

后面一部分只需要和儿子取 即可，考虑前一部分怎么算。

设点 为一对合法点对，则其贡献为 。

我们扫 ，然后维护 。

具体的，我们维护一个 ，表示 的最大的 。

在遍历到一个儿子 时，我们枚举哪一位为 ，若合法则更新答案。

删除轻儿子的贡献时，直接把对应的 清空即可。

复杂度 。

注意：计算答案时是类似点分治一样，算完这颗子树再把它合并进来，因为这样才能保证路径的 为 。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=5e5+10,maxv=(1<<22)+10,inf=1e18;
int n,m,sum,son;
int a[maxn];
int head[maxn],ans[maxn];
int mx[maxv];
struct node{
    int siz,hson,dep;
}t[maxn];
vector<pii> g[maxn];
inline void dfs1(int u){
    t[u].siz=1;
    for(auto x:g[u]){
        int v=x.fi,c=x.se;
        t[v].dep=t[u].dep+1;
        a[v]=a[u]^(1<<c);
        dfs1(v);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
}
inline void add(int u){
    mx[a[u]]=max(mx[a[u]],t[u].dep);
    for(auto x:g[u]){
        int v=x.fi;
        add(v);
    }
}
inline void get_ans(int u){
    sum=max(sum,t[u].dep+mx[a[u]]);
    for(re int i=0;i<22;++i) sum=max(sum,t[u].dep+mx[a[u]^(1<<i)]);
    for(auto x:g[u]){
        int v=x.fi;
        get_ans(v);
    }
}
inline void del(int u){
    mx[a[u]]=-inf;
    for(auto x:g[u]){
        int v=x.fi;
        del(v);
    }
}
inline void dfs(int u,bool op){
    for(auto x:g[u]){
        int v=x.fi;
        if(v==t[u].hson) continue;
        dfs(v,0);
    }
    if(t[u].hson) dfs(t[u].hson,1);
    sum=0;
    sum=max(sum,t[u].dep+mx[a[u]]);
    for(re int i=0;i<22;++i) sum=max(sum,t[u].dep+mx[a[u]^(1<<i)]);
    for(auto x:g[u]){
        int v=x.fi;
        if(v==t[u].hson) continue;
        get_ans(v),add(v);
    }
    ans[u]=sum-t[u].dep*2;
    for(auto x:g[u]){
        int v=x.fi;
        ans[u]=max(ans[u],ans[v]);
    }
    if(!op) del(u);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=2,fa;i<=n;++i){
        char c;cin>>fa>>c;
        g[fa].push_back({i,c-'a'});
    }
    for(re int i=0;i<(1<<22);++i) mx[i]=-inf;
    dfs1(1),dfs(1,0);
    for(re int i=1;i<=n;++i) cout<<max(0ll,ans[i])<<' ';
    return 0;	
}

Dominant Indices

思路和线段树合并的思路完全一样。

统计每个深度出现次数，然后取最大即可。

记得减一下。

Tree and Queries

套个树状数组支持查询即可。

复杂度 。

但事实上完全不需要这个树状数组，只需要开个桶即可。

具体的，维护一个数组 ，表示出现次数 的颜色数，然后再开一个数组维护每种颜色出现次数，就做完了。

Tree Requests

对每个深度维护每种字符出现次数的奇偶性即可。

复杂度 。

Blood Cousins Return

每个深度开个 set 即可。

注意是森林。

复杂度 。

≡