啟發式合并

将 n n n個集合進行合并，最後合并為1個集合

暴力合并

假設一次合并的時間複雜度為 O ( o p ) O(op) O(op)

合并過程中的複雜度為 O ( 1 + 2 + 3 ⋯ + n ) = O ( n 2 ) O(1 + 2 + 3 \dots+n) = O(n^2) O(1+2+3⋯+n)=O(n2)

總的時間複雜度為 O ( o p n 2 ) O(opn^2) O(opn2)

需要優化！

如果每一次将小的集合合并到大的集合裡面

複雜度為： O ( o p × n l o g n ) O(op \times nlogn) O(op×nlogn)

觀察每一個元素對最終計算量的貢獻

它取決于每一次所在集合合并的次數

假設最小的集合，集合内的元素個數為 x x x

合并一次之後，兩個集合合并之後元素個數為 2 ∗ x 2*x 2∗x

AcWing 2154. 夢幻布丁 - AcWing

題意：

n個布丁，有m個顔色

操作：

op1:要把一個顔色的布丁全部變為另一種顔色

op2:詢問連續的顔色段個數

每一次将 x x x的顔色變成 y y y，就代表 x x x和 y y y的珠子合并成同一類

計算一個珠子的貢獻，如果它變化前和左邊不一樣，則貢獻加一，如果和右邊不一樣，則貢獻為2。

合并之後，貢獻減2。

存儲時候，需要将每種顔色對應珠子的編号進行存儲。

每一次合并的時候，把小的集合鍊合并到大的集合鍊，并且維護顔色之間的包含關系

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m, ans;
int color[N], h[M], ne[N], e[N], id;
int fa[M], sz[M];

void add(int a, int b)
{
    e[id] = b, ne[id] = h[a], h[a] = id++;
    sz[a]++;
}

void merge(int &a, int &b)
{
    if(a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    for(int i = h[a]; i != -1; i = ne[i])
    {
        int j = e[i];
        ans -= (color[j - 1] == b) + (color[j + 1] == b);
    }
    for(int i = h[a]; i != -1; i = ne[i])
    {
        int j = e[i];
        color[j] = b;
        if(ne[i] == -1)
        {
            ne[i] = h[b];
            h[b] = h[a];
            break;
        }
    }
    sz[b] += sz[a];
    sz[a] = 0;
    h[a] = -1;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &color[i]);
        add(color[i], i);
    }
    ans = 1;
    for(int i = 2; i <= n; i++)
    {
        if(color[i] != color[i - 1]) ans++;
    }
    
    for(int i = 1; i < M; i++) fa[i] = i;
    
    while(m --)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            merge(fa[x], fa[y]);
        }
        else
        {
            printf("%d\n", ans);
        }
    }
    
    return 0;
}
           

3189. Lomsat gelral - AcWing題庫（樹上啟發式合并）

Problem

樹的節點有顔色，一種顔色占領了一個子樹，當且僅當沒有其他顔色在這個子樹中出現得比它多。求占領每個子樹的所有顔色之和 CF600E

solution

算法思路

這道題我們可以周遊整棵樹，并用一個 c n t cnt cnt數組記錄每種顔色出現幾次

但是每做完一棵子樹就需要清空 c n t cnt cnt，以免對其兄弟造成影響。

而這樣做它的祖先時就要把它重新搜一遍，浪費時間

但是我們發現，對于每個節點x，最後一棵子樹是不用清空的，因為做完那棵子樹後可以把其結果直接加入x的答案中。

選哪棵子樹呢？當然是所含節點最多的一棵咯，我們稱之為“重兒子”

考慮暴力怎麼寫：周遊每個節點—>把子樹中的所有顔色暴力統計出來更新答案—>消除該節點的貢獻—繼續遞歸這肯定是 O ( n 2 ) O(n^2) O(n2)的。

d s u o n t r e e dsu on tree dsuontree巧妙的利用了輕重鍊剖分的性質，把複雜度降到了 O ( n l o g n ) O(nlogn) O(nlogn)。你不知道啥叫輕重鍊剖分？一句話：對于樹上的一個點，與其相連的邊中，連向的節點子樹大小最大的邊叫做重邊，其他的邊叫輕邊

算法證明

設根到該節點有x條輕邊，該節點的大小為y，根據輕重邊的定義，輕邊所連向的點的大小不會成為該節點總大小的一半。這樣每經過一條輕邊，y的上限就會/2，是以 y < n / 2 x y<n/2^x y<n/2x，是log的。即一個節點到根的路徑上輕邊個數不會超過 l o g n logn logn條。是以最後的複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)

算法實作，對于節點i：

周遊每一個節點

遞歸解決所有的輕兒子，同時消除遞歸産生的影響

遞歸重兒子，不消除遞歸的影響

統計所有輕兒子對答案的影響

更新該節點的答案

删除所有輕兒子對答案的影響

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e5 + 50, M = N * 2;
int n;
int h[N], ne[M], e[M], id;
int son[N], mx, cnt[N], sz[N], color[N];
ll ans[N], sum;

void addedge(int u, int v)
{
    e[id] = v, ne[id] = h[u], h[u] = id++;
}

int dfs_son(int u, int father)
{
    sz[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        sz[u] += dfs_son(j, u);
        if(sz[j] > sz[son[u]]) son[u] = j;
    }
    return sz[u];
}

void update(int u, int father, int sign, int pson)
{
    // 計算每個結點的sum
    int c = color[u];
    cnt[c] += sign;
    if(cnt[c] > mx) mx = cnt[c], sum = c;
    else if(cnt[c] == mx) sum += c;
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father || j == pson) continue; // 更新的時候避開輕兒子
        update(j, u, sign, pson);
    }
}

void dfs(int u, int father, int op) // 重兒子op為1， 輕兒子op為2
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father || j == son[u]) continue; // 避開重兒子
        dfs(j, u, 0);  
    }
    
    if(son[u]) dfs(son[u], u, 1);
    update(u, father, 1, son[u]); // 重兒子不需要清空
    
    ans[u] = sum;
    
    if(!op) 
    {
        update(u, father, -1, 0); // 輕兒子需要清空
        sum = mx = 0; 
    }
}

int main()
{
    memset(h ,-1, sizeof(h));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &color[i]);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        addedge(a, b), addedge(b, a);
    }
    
    dfs_son(1, -1);
    dfs(1, -1, 1);
    
    for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
    
    return 0;
}