icontofig | 发布于 2020-04-05 16:24:36 | 阅读量 346 | dsu on tree 树链剖分
发布于 2020-04-05 16:24:36 | dsu on tree 树链剖分

Example

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

题目大意

给出一棵有根树,树上每个点有一个颜色,求问以每一个节点x为根的子树内数量最多的颜色的编号的和sum为多少。

题解

如果暴力统计的话,时间复杂度将会成为O(n2),这是我们没办法接受的。

貌似可以搞什么线段树合并还有莫队什么的。

但是复杂度好像依旧还是太高,于是就有这么一个神奇的东西叫dsu on tree,中文名叫树上启发式合并。

dsu实际上是并查集的问题,但这个算法并不是什么树上并查集,而是借鉴了并查集中启发式合并优化的思想,将这个思想运用到了树上。

结合树链剖分的性质,将所有的树链分为轻链和重链后,对于每一个子树的根节点rt:轻链子节点sq,递归进入计算以sq为根的子树的答案,但是不保存,递归结束时清空;重链子节点son,递归进入计算以son为根的子树的答案,递归结束时不清空,作为rt为根节点的子树的基础答案。

之后对于以rt为根节点的子树,在重链子节点son的子树提供的基础答案上,再暴力计算该子树其它所有轻链子树和rt节点本身的答案,与刚刚的基础答案合并,可以解算出以rt为根节点的子树的答案。

通过树链剖分的轻重链性质,不难证明答案的复杂度应该为O(nlog2n),因为所有节点被访问的次数至多为log2n次。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int x,y;
typedef long long ll;
ll ans[maxn],c[maxn],sum,mx;
int son[maxn],siz[maxn],f[maxn],cnt[maxn];
vector<int>g[maxn];
int n,s;
void dfs(int now,int fa){
    f[now] = fa;
    siz[now] = 1;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now] += siz[it];
        if(siz[it] > siz[son[now]])
            son[now] = it;
    }
    return;
}
void cal(int now,int fa,int d){
    cnt[c[now]] += d;
    if(cnt[c[now]] == mx){
        sum += c[now];
    }
    else if(cnt[c[now]] > mx){
        mx = cnt[c[now]];
        sum = c[now];
    }
    for(auto it : g[now]){
        if(it == fa || it == s)continue;
        cal(it,now,d);
    }
    return;
}
void work(int now,int fa,int flag){
    for(auto it : g[now]){
        if(it != f[now] && it != son[now])
            work(it,now,0);
    }
    if(son[now]){
        work(son[now],now,1);
        s = son[now];
    }
    cal(now,fa,1);
    ans[now] = sum;
    s = 0;
    if(!flag){
        cal(now,f[now],-1);
        sum = 0;
        mx = 0;
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> c[i];
        g[i].clear();
        son[i] = siz[i] = f[i] = ans[i] = 0;
    }
    for(int i = 1;i < n;++i){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    sum = mx = 0;
    work(1,1,0);
    cout << ans[1];
    for(int i = 2;i <= n;++i){
        cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}



内容更新于: 2020-04-05 16:24:36
链接地址: http://blog.leanote.com/post/icontofig/CodeForces-600E-Lomsat-gelral

上一篇: 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift

下一篇: HDU6417 Rikka with APSP min25筛+mobius反演

346 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航