A Huster

0%

dsu on tree

Posted on Valine:

这篇博客只是简单叙述思想(因为ML太弱了),具体例题请转其他博客.

dsu on tree,许多OI将其归于启发式合并,当然如果你能理解更好,这只是一个理解方式罢了.

思想简述

　　顾名思义,这个算法是处理树上问题,将子树分开求解,如果暴力了话是枚举每个子树,然后dfs;

　　这里将每次dfs完的清空操作重新定义,并且规定dfs顺序,以来优化成log解法.

　　这里我们引入一个 例题

一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和。

　　仔细读题我们可以先想到暴力解法,分别从一个点进行dfs,肯定会爆;

　　那么我们思考一下,一颗子树上的点dfs结果是否可以被该子树根节点利用?

　　当然可以,但是我们只能保留一个点的结果,所以我们就面临一个选择,留哪一个?

　　我们想到树剖,那么我们保留重儿子就可以较好的保留信息,时间复杂度也会大幅降低.

操作步骤

　　1.dfs1找到重儿子和轻儿子;

　　2.dfs2递归处理每一个点,先扫描轻儿子,再扫描重儿子.

　　3.设计calc函数,用来处理轻重儿子,可以将add和del分开写,也可以合在一起;

代码实现

　　

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
#include<bits/stdc++.h>
#define maxn 100007
#define ll long long
using namespace std;
int n,head[maxn],a[maxn],sz[maxn],son[maxn],cent;
int fa[maxn],vis[maxn];
ll col,max_part,num[maxn],ans[maxn];
struct node{
    int next,to;
}edge[maxn<<2];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
template<typename type_of_print>
inline void print(type_of_print x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline void add(int u,int v){
    edge[++cent]=(node){head[u],v};head[u]=cent;
    edge[++cent]=(node){head[v],u};head[v]=cent;
}

void dfs1(int x){
    sz[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa[x]) continue;
        fa[y]=x;dfs1(y);sz[x]+=sz[y];
        if(sz[son[x]]<sz[y]) son[x]=y;
    }
}

void calc(int x,int p){
    num[a[x]]+=p;
    if(p>0&&num[a[x]]==max_part) col+=a[x];
    if(p>0&&num[a[x]]>max_part) col=a[x],max_part=num[a[x]];
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa[x]||vis[y]) continue;
        calc(y,p);
    }
}

void dfs2(int x,int id){
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,0);
    }
    if(son[x]) dfs2(son[x],1),vis[son[x]]=1;
    calc(x,1);ans[x]=col;
    if(son[x]) vis[son[x]]=0;
    if(!id) calc(x,-1),max_part=col=0;
}

int main(){
    scan(n);
    for(int i=1;i<=n;i++) scan(a[i]);
    for(int i=1,u,v;i<=n-1;i++)
        scan(u),scan(v),add(u,v);
    dfs1(1),dfs2(1,1);
    for(int i=1;i<=n;i++) print(ans[i]),putchar(' ');
}
本站访问次数：