Tag-dsu on tree

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-04-05 16:24:36 |  0 Comments  |  dsu on tree 树链剖分

CodeForces 600E.Lomsat gelral 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
Title - Artist
0:00