Dsu On Tree-启发式树上合并

简介

1. 可以解决区间众数问题
2. 不能支持修改,只能支持子树统计，不能链上统计。
3. 和并查集无关

理解

假设给定一棵树，每个节点都有自己的颜色，现多次询问要求以某结点为根的子树内数量最多的颜色的编号。暴力即是对于询问
的每一个节点递归统计颜色求最大，但是如果数据过大即使预处理各节点答案也可以导致n²复杂度。考虑每个节点的求解过程，都是要统计完子树的才更新自己，我们如果把统计子树内颜色个数的数组定为cnt，则cnt在一个子树用完后被另一个子树用时必须清空，这导致了低效。可以发现统计子树的颜色时，最后一个被统计的子树不必被清空，这在递归中自然不好特判，但我们可以利用这个性质，先求出非重子树的贡献，清空cnt，再求出重子树cnt，并利用这时的cnt再跑一遍非重子树加上其贡献。复杂度可以达到令人惊讶的O(nlogn);

Lomsat gelral

分析

已经分析了吧...

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid  ((L + R) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
    char c = getchar(),f = 1;x = 0;
    for(;c ^ '-' && !isdigit(c);c = getchar());
    if(c == '-') c = getchar(),f = -1;
    for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
    x *= f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn = 100010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
struct edge{
    int to,last;
}e[maxn<<1];
int head[maxn],tot;
void add(int from,int to) {
    ++tot;
    e[tot].to = to;
    e[tot].last = head[from];
    head[from] = tot;
}
int siz[maxn],son[maxn];
void dfs(int x,int da) {//重链剖分 
    siz[x] = 1;
    for(rint i = head[x]; i; i = e[i].last) {
        if(e[i].to == da) continue;
        dfs(e[i].to,x);
        siz[x] += siz[e[i].to];
        if(son[x] == 0 || siz[son[x]] < siz[e[i].to]) son[x] = e[i].to;
    }
    return ;
}
int cnt[maxn];
ll sum,ans[maxn],Mx,Tem,col[maxn];
void deal(int x,int da,int val) {
    cnt[col[x]] +=val;//因题而异 
    if(cnt[col[x]] > Mx) Mx = cnt[col[x]],sum = col[x];
    else if(cnt[col[x]] == Mx) sum += col[x];
    for(rint i = head[x]; i; i = e[i].last) {
        if(e[i].to == da || e[i].to == Tem) continue;
        deal(e[i].to,x,val);
    }
}
void ddfs(int x,int da,int opt) {
    for(rint i = head[x]; i; i = e[i].last) {
        if(e[i].to == da) continue;
        if(e[i].to ^ son[x]) ddfs(e[i].to,x,0);//暴力统计轻边的贡献，opt = 0表示递归完成后要消除对该点的影响
    }
    if(son[x]) ddfs(son[x],x,1),Tem = son[x];//统计重儿子的贡献，不消除影响
    deal(x,da,1);Tem = 0;//暴力统计所有轻儿子的贡献
    ans[x] = sum;//更新答案 
    if(!opt) deal(x,da,-1),sum = 0,Mx = 0;//如果需要删除贡献的话就删掉
    return ; 
}
int n;
int main()
{
    read(n);
    for(rint i = 1;i <= n; ++i) read(col[i]);
    for(rint i = 2;i <= n; ++i) {
        int x,y;
        read(x);read(y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    ddfs(1,0,0);
    for(rint i = 1;i <= n; ++i) print(ans[i]),putchar(' ');
    return 0;
}
/*

*/

推荐博客

Dsu On Tree-启发式树上合并

原文：https://www.cnblogs.com/Thomastine/p/11815203.html