抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Dsu on tree

发布于：2022年8月17日

dsu on tree

树上莫队（迫真

树上启发式合并 dsu on 🌳

一般用来处理一些带有如下特征的树上问题

  • 不带修
  • 对于子树的询问

考虑 O(n2)O(n^2) 暴力，遍历节点子树统计答案，然后清除子树的贡献防止对它的兄弟造成影响

我们发现有一棵子树的贡献可以不清空，直接递归加到当前节点的贡献里

显然是不清空的子树越大越好，所以考虑重链剖分，保留节点重儿子所在的子树

算法流程：

预处理出每个节点的重儿子

递归统计轻儿子答案，清除

统计重儿子的答案，不清除贡献

最后统计当前节点的答案，因为清楚了轻儿子的贡献，要再加回来

dsu on tree 就是版子，统计和清除贡献需要灵活运用

CF375D

给定一棵 nn 个节点的树，根节点为 11。每个节点上有一个颜色 cic_i。mm 次操作。每次询问在以 uu 为根的子树中，出现次数 ≥k\ge k 的颜色有多少种

纯纯滴板子，维护两个桶

cnt[i] 表示颜色 i 的出现次数

cntt[i] 表示出现次数大于等于 i 的颜色有多少个

Code 
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n, m, c[MAXN];
int siz[MAXN], son[MAXN];
int cnt[MAXN], cntt[MAXN];
int ans[MAXN], Ans;
namespace F_star
{
    int cnte = 0, head[MAXN];
    struct edge
    {
        int to, nxt;
    }e[MAXN << 1];
    void adde(int u, int v)
    {
        e[++cnte].to = v;
        e[cnte].nxt = head[u];
        head[u] = cnte;
    }
}using namespace F_star;
struct query
{
    int id, val;
};
vector <query> v[MAXN];

void dfs(int u, int fa)
{
    siz[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v; 
    }
}

//加单点贡献，删单点贡献
void add(int u)
{
    cnt[c[u]]++;
    cntt[cnt[c[u]]]++;
}
void del(int u)
{
    cntt[cnt[c[u]]]--;
    cnt[c[u]]--;
}
//加子树贡献，删子树贡献
void adds(int u, int fa)
{
    add(u);
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(v == fa) continue;
        adds(v, u);
    }
}
void clannad(int u, int fa)
{
    del(u);
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(v == fa) continue;
        clannad(v, u);
    }
}

void dsu(int u, int fa)
{
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa || v == son[u]) continue;
        dsu(v, u); clannad(v, u); //递归统计轻儿子答案，并清除贡献
    }
    if(son[u]) dsu(son[u], u); //统计重儿子答案
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa || v == son[u]) continue;
        adds(v, u); // 把轻儿子贡献加进来
    }
    add(u); //加入当前节点
    for(int i = 0; i < v[u].size(); i++)
    ans[v[u][i].id] = cntt[v[u][i].val];
}

int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++) scanf("%d",&c[i]);
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adde(u, v); adde(v, u);
    }

    for(int i = 1; i <= m; i++)
    {
        int u, k;
        scanf("%d%d",&u,&k);
        v[u].push_back(query{i, k});
    }
    dfs(1, 0); dsu(1, 0);
    
    for(int i = 1; i <= m; i++)
    printf("%d\n", ans[i]);
    return 0;
}

CF600E

给定一棵 nn 个节点的树，根节点为 11。每个节点上有一个颜色 cic_i。询问子树内出现次数最多的颜色的编号和

稍微不是那么板，但还是该咋办咋办，用一个栈维护出现了哪些颜色，动态维护最大值即可

Code 
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>

#define MAXN 100005
#define ll long long

using namespace std;
int n;
int c[MAXN], cnt[MAXN], maxt;
ll ans[MAXN], Ans;

namespace F_star
{
    int cnte = 0, head[MAXN];
    struct edge
    {
        int to, nxt;
    }e[MAXN << 1];
    void adde(int u, int v)
    {
        e[++cnte].to = v;
        e[cnte].nxt = head[u];
        head[u] = cnte;
    }
    
}using namespace F_star;

int siz[MAXN], son[MAXN];
void dfs(int u, int fa)
{
    siz[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;    
    }
}

int sta[MAXN], top;

//清空贡献
void clannad()
{
    while(top) cnt[sta[top--]] = 0;
    maxt = Ans = 0;
}
void add(int u)
{
    ++cnt[c[u]];
    sta[++top] = c[u];
    
    //加入贡献并处理答案
    if(cnt[c[u]] > maxt)
    {
        maxt = cnt[c[u]];
        Ans = c[u];
    }
    else if(cnt[c[u]] == maxt) Ans += c[u]; 
}

void adds(int u, int fa)
{
    add(u);
    for(int i = head[u]; i; i = e[i].nxt)
    {
        if(e[i].to != fa) 
        adds(e[i].to, u);
    }
}

void dsu(int u, int fa)
{
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == son[u] || v == fa) continue;
        dsu(v, u); clannad();
    }
    if(son[u]) dsu(son[u], u);
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == son[u] || v == fa) continue;
        adds(v, u);
    }
    add(u);
    ans[u] = Ans;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    scanf("%d",&c[i]);
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        adde(u, v); adde(v, u);
    }
    dfs(1, 0);
    dsu(1, 0);
    for(int i = 1; i <= n; i++)
    printf("%lld ",ans[i]);

    return 0;
}
Dsu on tree
https://ve1bae.github.io/2022/08/17/Dsu-on-tree/
本文作者
Veibae
发布于
2022年8月17日
更新于
2022年11月8日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

更新于：2022年11月8日

dsu on tree

评论