Codeforces 600E Lomsat gelral(dsu on tree树上启发式合并)

题意

给一颗有根树,节点有颜色,求每个点子树内出现次数最多的颜色的权值(有多个就是权值和)。

1 ≤ n ≤ 105 

1 ≤ ci ≤ 权值

题解

考虑暴力的做法,对于每个节点直接遍历,将颜色放入桶,统计答案。这样复杂度是n2的。

怎么去优化呢?可以看到每次遍历完一棵子树,我们都是把桶清空再重新遍历,其实他的有些信息是可以保留的。

如何就出现了一种做法,对于整个树先dfs一遍找出每个点的重儿子(同树链剖分)

我们再遍历时,从根遍历,先进轻儿子所在子树,统计轻儿子的答案,然后将桶清除。

然后再进重儿子所在子树,统计重儿子答案,不清除桶。

接着再把轻儿子和他本身加入桶,统计答案。

看上去也很暴力,那为什么时间复杂度是对的呢?

遇到一条轻边,就会把整个子树加入一遍,对于每个点,他到根的轻边条数就是他被加入的次数,所以复杂度nlgn

Codeforces 600E    Lomsat gelral(dsu on tree树上启发式合并)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100005;
int n;
int co[maxn];
int size[maxn],fa[maxn],son[maxn];
ll get_it[maxn],ans;
int cx[maxn],num;
vector<int>e[maxn];

void dfs(int u){
    size[u]=1;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs(v);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

void clear(int u){
    cx[co[u]]--;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        clear(v);
    }
}

void add(int u){
    cx[co[u]]++;
    if(cx[co[u]]>num) ans=co[u],num=cx[co[u]];
    else if(cx[co[u]]==num) ans+=co[u];
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        add(v);
    }
}

void get_ans(int u){
    if(!u) return ;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]||v==son[u]) continue;
        get_ans(v);
        ans=0;num=0;
        clear(v);
        //for(int i=1;i<=n;i++) printf("%d ",cx[i]);
        //putchar(10);
    }
    get_ans(son[u]);
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==son[u]||v==fa[u]) continue;
        add(v);
    }
    cx[co[u]]++;
    if(cx[co[u]]>num) ans=co[u],num=cx[co[u]];
    else if(cx[co[u]]==num) ans+=co[u];
    get_it[u]=ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&co[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    get_ans(1);
    for(int i=1;i<=n;i++) printf("%I64d ",get_it[i]);
}
View Code

 

上一篇:【2019.10.25】


下一篇:练习赛42