樹上啟發式合併

DSU on tree，我也不知道DSU是啥意思

這是一種看似特別玄學的優化

可以把樹上部分問題由 \(O(n^2)\) 優化到 \(O(n \log n)\)。

例如 CodeForces 600E。

又例如一道神奇的題：

適用情況

可以離線的部分樹上問題。

需要子樹上的所有資訊，但是資訊無法快速合併的情況。

或者說可以使用樹上莫隊的題目一般都可以使用啟發式合併？（至少OI-Wiki是這麼說的）

樹上啟發式合併並不是很常用

合併思路

首先定義一點概念：

重子節點：一個結點的子結點中度最大的結點~~（孩子個數最多的點）~~
輕子節點：非重子節點的節點
重邊：重子結點（如果有）與其父結點相連的邊
輕邊：非重邊
重鏈：相鄰重邊連結形成的鏈~~（這裡好像用不到）~~

樹上啟發式合併的思路如下：

處理 x 為根的情況
遞迴處理 輕子節點 的答案，並捨棄其資訊
處理 重子節點 的答案，並保留其資訊
如果 x 為（其父親的）重子節點，則加上所有 輕子節點 的資訊。否則捨棄其資訊

很明顯，我們需要預處理出重子節點。同時可能需要用到 dfn 序來優化資訊的加入

不妨我們以 vector 存圖（非常方便）
void workSon(int x, int f) {
    siz[x] = 1, fa[x] = f;
    dfn[x] = ++cdfn, rdfn[cdfn] = x;
    for (int y : G[x]) {
        if (dfn[y]) continue;
        workSon(y, x);
        siz[x] += siz[y];
        if (siz[son[x]] < siz[y]) son[x] = y;
    }
    edfn[x] = cdfn;
}
最終 son[x] 就是 x 的重子節點，同時我們處理出了 dfn 序以及以 x 為子樹的 dfn 序範圍：[dfn[x], edfn[x]] ~~注意為閉區間~~

那麼虛擬碼大致如下：

// remain 用於獲知需不需要保留資料，預設不保留
int currentAnswer;
void work(int x, bool remain = false) {
    for (int y : G[x]) {
        if (y != fa[x] && y != son[x]) work(y);
    }

    if (son[x]) work(son[x], true);

    for (int y : G[x]) {
        if (y == fa[x] || y == son[x]) continue;
        addSubTreeInfoAndUpdateAnswer(y);
    }

    answerOf[x] = currentAnswer;
    if (!remain) {
        clearAnswer();
        for (int y : G[x]) {
            if (y != fa[x]) removeSubTreeInfo(y);
        }
    }
}

每個部分的作用在函數名裡面應該很清晰了。這裡不再贅述。

複雜度證明

首先，根節點到樹上任意節點的輕邊數不超過 \(\log n\) 條。

只有當祖先節點為輕子節點時其資訊會被刪除。也就是加入 \(O(\log n)\) 次，刪除 \(O(\log n)\) 次，故而每一個點的複雜度為 \(O(\log n)\)，整體的複雜度為 \(O(n \log n)\)。

當然，考慮如果每一個節點加入資訊或者刪除資訊的複雜度為 \(O(k)\)，則整體複雜度為 \(O(n k \log n)\)。

非常玄學……但是就是能夠優化

例題分析

就以開始為例子的兩道題為例吧。

CodeForces 600E

這道題也就是樹上數顏色的問題。

題目大意是：

對於每一個節點，做出貢獻的顏色需要滿足出現的次數是最多的之一。一個顏色的貢獻即是這個顏色的編號。

最終輸出每一個節點被貢獻的結果

最主要也是最重要的就是顏色的統計。

加入點（顏色）的核心程式碼如下：

int colorBut[N];
long long maxExi = 0, cnt = 0;
void add(int c) {
    if (++colorBut[c] == maxExi) {
        cnt += c;
    } else if (colorBut[c] > maxExi) {
        maxExi = colorBut[c], cnt = c;
    }
}

在合併部分也很清晰了

long long res[N];
void dsu(int x, int f, bool remain = false) {
    for (int y : G[x]) {
        if (y != f && y != son[x]) dsu(y, x);
    }

    if (son[x]) dsu(son[x], x, true);

    // 記得把根節點的資訊也加進去！
    add(col[x]);
    for (int y : G[x]) {
        if (y == f || y == son[x]) continue;
        // 新增資訊
        for (int i = dfn[y]; i <= edfn[y]; ++i) add(col[rdfn[i]]); 
    }

    res[x] = cnt;
    if (!remain) {
        maxExi = cnt = 0; // 重置答案
        for (int i = dfn[x]; i <= edfn[x]; ++i) // 刪除影響資訊
            colorBut[col[rdfn[i]]] = 0;
    }
}

不正常國家

這道題稍微複雜一點。

考慮每對點對其 LCA 的貢獻。或者換個思路，考慮每一個根節點能夠被那些點貢獻。

不難發現，有兩種情況：

LCA 和其子節點之間的路徑
LCA 的兩個子節點之間的路徑。這裡要保證兩個子節點在不同的子樹裡面。

如果我們已經預處理出了樹上互斥或字首和 path。那麼任意兩個點對其 LCA 的貢獻為 path[x] ^ path[y] ^ val[LCA]。我們不妨對於每一個 LCA，列舉所有 path[y] ^ val[LCA]，同時在已知的 path[x] 中匹配最大的互斥或對。

最大互斥或對可以看此題：AcWing 143.最大互斥或對

利用了01Trie樹和二進位制貪心。

此處不展開。

同時，由於我們需要保證 x 和 y 在 u 的不同子樹中，所以我們先查詢完一顆子樹再加入這棵子樹的資訊。

核心程式碼如下：

// 樹上啟發式合併 
void work(int x, int f, bool remain = false) {
    // 首先搞定所有非重子節點
    for (int y : G[x]) {
        if (y == f || y == son[x]) continue;
        work(y, x);
    }

    // 搞定重子節點，並保留資料 
    if (son[x]) work(son[x], x, true);
    // path[fa[x]] 也就是 path[x] ^ val[x]
    int ans = max(val[x], trie.pairMax(path[fa[x]]));
    trie.insert(path[x]);

    // 加入其他節點，並搜尋
    for (int y : G[x]) {
        if (y == f || y == son[x]) continue;
        for (int j = dfn[y]; j <= edfn[y]; ++j) {
            int pa = path[rdfn[j]] ^ val[x];
            ans = max(ans, trie.pairMax(pa));
        }

        for (int j = dfn[y]; j <= edfn[y]; ++j) {
            trie.insert(path[rdfn[j]]);
        }
    }

    res[x] = ans;
    if (!remain) trie.clear();
}

至於 01Trie 樹程式碼如下：

const int LOG = 30; // 31位元！下標為 [0, 30]

#define bit(x, i) ((x >> i) & 1)
class Trie01 {
private:
    int ch[N << 4][2];
    int usage;
public:
    Trie01() : usage(1) {
    }

    inline int newNode() {
        ++usage;
        ch[usage][0] = ch[usage][1] = 0;
        return usage; 
    }

    void insert(int x) {
        int p = 1;
        for (int k = LOG; k >= 0; --k) {
            int s = bit(x, k);
            if (!ch[p][s]) ch[p][s] = newNode();
            p = ch[p][s];
        }
    }

    // 這是通過樹的形狀貪心尋找最大互斥或對
    int pairMax(int x) {
        int p = 1;
        int r = 0;
        for (int k = LOG; k >= 0; --k) {
            int s = bit(x, k) ^ 1;
            if (ch[p][s]) r = (r << 1) | 1, p = ch[p][s];
            else if (ch[p][s ^ 1]) r <<= 1, p = ch[p][s ^ 1];
            else p = 0, r = x; // 避免空樹的情況
        }
        return r;
    }

    void clear() {
        usage = 1;
        ch[1][0] = ch[1][1] = 0;
    }
} trie;

那麼這道水題也就這麼水過去了。

忘了說，其複雜度為 \(O(n \log n L)\)，其中 \(L\) 是位長，也就是程式碼中的 LOG = 30。所以複雜度也可以寫為 \(O(n \log^2 n)\)

樹上啟發式合併的潛力不止於此，還望諸君發掘。