树上启发式合并/DSU on tree

发表于 | 分类于 |

前置知识:树的重链剖分与并查集操作

与启发式搜索类似，树的启发式合并是由人的主观思维想到的，通过一些小操作使得合并子树答案时的复杂度尽可能降低。

回顾并查集操作，我们可以记录集合的size，合并两个集合时，将小size的集合指向大size的集合，以此降低集合深度，以减小查询时的复杂度，树的启发式合并也类似

引入问题，给定一颗树，每个节点都有点权，有q个查询，查询给出节点的编号，回答该节点每个子树中，点权的众数之和(注意，一颗子树可能有多个众数)

考虑用dfs统计，由于要求统计每颗子树，故我们已求出子树的统计结果必须消除，否则会影响其他子树的统计，复杂度为O(N^2)

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
void dfs(int u,int fa)
{
    add(u,fa,1);
    add(u,fa,-1);
    ans+=sum;//统计以u为根子树对答案的贡献
    sum=0;
    mx=-1;
    for(auto e:g[u])
    {
        if(e!=fa)
        {
            dfs(e,u);
        }
    }
}
void add(int u,int fa,int val)
{
    num[col[u]]+=val;
    if(num[col[u]]>mx)
    {
        mx=num;
        sum=col[u];
    }else if(num[col[u]]==mx)
    {
        sum+=col[u];//多个众数的情况
    }
    for(auto e:g[u])
    {
        if(e!=fa)
        {
            add(e,u,val);
        }
    }
}

想要优化这个暴力，我们易想到，规定根节点为rt，其重儿子为big，我们统计rt的众数时，可以保留最后一个儿子的统计结果(此时不会影响其他儿子的统计结果了)，而不消除，进而优化时间，保留的儿子size最好尽可能大，故保留big的统计结果

故修改后代码如下:

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
void add(int u,int fa,int val)
{
    num[col[u]]+=val;
    if(num[col[u]]>mx)
    {
        mx=num;
        sum=col[u];
    }else if(num[col[u]]==mx)
    {
        sum+=col[u];
    }
    for(auto e:g[u])
    {
        if(e!=fa&&e!=SON)//注意添加了SON的判断
        {
            add(e,u,val);
        }
    }
}
void dfs(int u,int fa,bool ok)//添加ok来判断当前节点回溯时是否保留
{
    for(auto e:g[u])
    {
        if(e!=fa&&e!=son[u])
        {
            dfs(e,u,0);//轻儿子统计后即删除
        }
    }
    if(son[x])
    {
        dfs(son[x],u,1);//重儿子统计后不删除
        SON=son[x];//统计本节点子树时不统计SON
    }
    sum=0;
    mx=-1;
    add(u,fa,1);//统计节点子树
    ans+=sum;
    if(!ok)
    {
        SON=-1;
        add(u,fa,-1);//轻儿子回溯时删除
    }
}

分析一下时间复杂度，给定一个节点，若其通过重链被访问，则其最多被统计一次，若通过轻链被访问，则其到根节点最多有logN个轻链，故最多统计logN次，故总复杂度为O(NlogN)

总结:树的启发式合并适用于1.无修改2.统计子树情况

PS:该题也可将树的节点用dfs序转换成区间查询问题后采用莫队算法

大部分内容参考来源:

https://blog.csdn.net/qq_46030630/article/details/120555851

https://www.cnblogs.com/zwfymqz/p/9683124.html

https://blog.csdn.net/qaq__qaq/article/details/53455462