Centroid Decomposition & Tree Hash

Centroid Decomposition

重心剖分 (樹分治)，透過每次不斷找到當前子圖的重心，重心拔掉再遞迴下去分割的子樹找各自的重心

重心的定義為一棵樹把節點 \(G\) 移除之後，其最大的連通塊會是最小的，而我們會稱節點 \(G\) 是樹重心。

如何找到樹重心

先選一個點為根節點，暴力 \(O(n)\) 跑過所有節點紀錄每個節點的子樹大小 \(s_i\)。

假設子樹大小分別為 \(s_1, s_2,... s_k\)，則父節點方向的子樹大小為 \(n - 1 - \sum{s_i}\)

樹重心為 max(n-1-\(\sum{s_i}, s_1, s_2...s_k)\) 中最小的節點

重心的性質

• 把重心拔掉之後, 所有子樹的大小會 \(\le\frac{n}{2}\)

• 一棵樹最多兩個樹重心

重心剖分

1. 找到樹重心
2. 把樹重心從圖上移除
3. 遞迴下去連到的子圖
4. 如果子圖大小 >1 回到步驟 1

找到樹重心

把樹重心從塗上移除，剩下的子圖分別去找各自的樹重心

找到子圖各自的樹重心

把樹重心移除，剩下的子圖分別去找個字的樹重心

找到各自的樹重心

複雜度

每次把圖從重心分割，每個子圖最大為原本的一半
最多遞迴 \(\log N\) 層

\(T(n)=\sum T(s_i) + O(n)\)

複雜度 \(O(N\log{N})\)

重心樹

對於當前這層的重心與下一層子圖的重心連接可以構出一顆重心樹

由於重心剖分的性質，樹高度不超過 \(\log n\)

\(\to\)

\(\to\)

引入例題

CF 342 E. Xenia and Tree

給你 \(n\) 個節點的樹，一開始每個點都是藍色，會有 \(m\) 次操作

• 把某個藍點塗成紅色
• 查詢某個點最近的紅點有多遠。

\(n, m\le 10^5\)

\(n, m\le 10^5\)

如果暴力做，直接用一個陣列紀錄每個節點的顏色

• 把某個藍點塗成紅色 \(\to\) O(1) 更新某個節點的顏色

• 查詢某個點最近的紅點 \(\to\) BFS 找最近的紅色節點 \(O(n)\)

很明顯如果每次都是第二種操作，總複雜度為 \(O(nm)\to\) TLE

換一種作法

先選一個節點為根
每個節點紀錄到子樹中最近的紅色節點距離，沒有則視為無限大

1. 把某個藍點 \(v\) 塗成紅色
   • 從當前節點 \(v\) 開始往根節點方向更新所有祖先的距離

2. 查詢某個點 \(v\) 最近的紅點
   • 從當前節點 \(v\) 開始往上走
   • 每次判斷到某個祖先 \(u\) 的距離 + 祖先 \(u\) 到他最近的子樹紅色節點距離取最短的

1. 把某個藍點 \(v\) 塗成紅色

   • 從當前節點 \(v\) 開始往根節點方向更新所有祖先的距離

2. 查詢某個點 \(v\) 最近的紅點

   • 從當前節點 \(v\) 開始往上走
   • 每次判斷到某個祖先 \(u\) 的距離 + 祖先 \(u\) 到他最近的子樹紅色節點距離取最短的

以上兩種 case 只要到根節點距離很遠複雜度就變 \(O(n)\)

一樣最差會變成 \(O(nm)\)

但如果樹是平衡的 ?

如果樹高最高為 \(\log n\)

1. 把某個藍點 \(v\) 塗成紅色

   • 從當前節點 \(v\) 開始往根節點方向更新所有祖先的距離

2. 查詢某個點 \(v\) 最近的紅點

   • 從當前節點 \(v\) 開始往上走
   • 每次判斷到某個祖先 \(u\) 的距離 + 祖先 \(u\) 到他最近的子樹紅色節點距離取最短的

則複雜度變成 \(O(m \log n)\)

用剛剛的重心樹 ?

會發現重心剖分建出來的重心樹樹高最差為 \(\log n\)

\(\to\)

把節點 \(v\) 塗成紅色

用 mn 陣列紀錄子樹中最近的紅色節點距離，沒有則視為無限大

對於每一次塗色，從當前節點往祖先方向走到重心樹根節點
更新從塗色節點 \(v\) 到當前走訪到的節點 \(u\) 距離是否為更近的紅色節點
mn[u] = min(mn[u], dis(u, v))

以塗色節點 5 為例

會更新節點 5, 4, 1 到紅色的最短

詢問節點 \(v\) 到最近紅色節點距離

從當前節點往重心樹根節點方向走
每次問走訪到的節點 \(u\) 與詢問節點 \(v\) 的距離+走訪到的節點 \(u\) 到子樹中最近的紅色節點距離
ans = min(ans, dis(u, v) + mn[u])

詢問節點 7 到紅色最短

答案會是

min( 節點 7 到最近紅色點距離, 
     節點 1 到最近紅色點距離 + 節點 1 到節點 7 的距離)
= min(∞, 2+2) = 4

為甚麼這樣是好的 ?

只更新從當前節點到重心樹根結點路徑上的距離，其他節點呢 ?

可以分成兩種 case :

1. 最近的紅色節點在重心樹的子樹中
2. 最近的紅色節點在往根節點方向

1. 最近的紅色節點 \(u\) 在重心樹的子樹中

如果節點 \(u\) 在詢問節點 \(v\) 的子樹中
則在塗色時已經更新過詢問節點 \(v\) 到最近紅色節點的距離

因此答案為 mn[v] = dis(u, v)

2. 最近的紅色節點 \(u\) 在往根節點方向

則到最近的紅色節點必定會先經過詢問節點 \(v\) 的某個祖先 \(a\)
因此答案為祖先 \(a\) 的子樹中最近的節點 + 自己到祖先 \(a\) 的距離

mn[a] + dis(a, v)

複雜度

每次會從當前節點走到重心樹的根節點
每次會計算樹上兩點之間的距離更新最近距離

由於樹高不超過 \(\log n\)

算樹上兩點之間的距離可以 \(O(\log n)\) 找 lca，
再透過深度 dep[u]+dep[v]-2*dep[lca] 得到

因此每次操作的複雜度為 \(O(\log^2n)\)
總複雜度為 \(O(m\log ^2n)\)

細節

注意計算距離是算原本那棵樹上的距離

另外一個例題

CSES. Fixed-Length Paths I

給一棵 \(N\) \((1\le N\le 2\cdot 10^5)\) 個節點的無根樹，樹上有幾個點對的距離為 \(k\)

也就是有幾個長度為 \(k\) 的簡單路徑

考慮分治

選一個點 \(v\) 計算所有經過他且長度為 \(k\) 的路徑
把點 \(v\) 拔掉再分成各自的連通子圖遞迴下去計算長度為 \(k\) 的路徑

經過當前點 \(v\) 的且長度為 \(k\) 的路徑分成兩種

1. 以當前點 \(v\) 為起點往外的路徑
2. 經過當前點 \(v\) 的且不為起始點的路徑

1. 以當前點 \(v\) 為起點往外的路徑

第一種我們可以從點 \(v\) 開始 DFS 紀錄從點 \(v\) 到當前節點的長度，如果長度為 \(k\) 則答案 + 1

auto dfs = [&](int x, int f, int d) -> void{
    if(d == k)     ++ans;
    for(int i : edge[x]){
        if(i == f || vis[i])    continue;
        dfs(i, x, d+1);
    }
};
for(int i : edge[v]){
    dfs(i, v, 1);    // 遞迴從 v 連出去的節點 i
}

2. 經過當前點的且不為起始點的路徑

第二種等價於從點 \(v\) 開始往兩棵相異子樹方向長度分別為 \(a, b\)
且 \(a+b = k\) 的路徑

我們可以算往某個子樹長度為 \(a\) 的路徑有幾個，乘上往其他子樹路徑長度為 \(k-b\) 有幾個。 每個子樹都去計算即為答案

每次從點 \(v\) 開始往不同的子樹去遞迴，計算每個子樹當前走到的距離 \(d\) 與前面計算過有幾個距離為 \(k-d\) (儲存在 cnt 陣列裡)

算完之後再把當前子樹的距離加進去 cnt 陣列裡

auto dfs = [&](int x, int f, int d, bool add) -> void{
    if(d == k){    //case 1
        ans++; return;
    }
    if(add)    ans += cnt[k - d];
    else       cnt[d]++;
    for(int i : edge[x]){
        if(i == f || vis[i])    continue;
        dfs(i, x, d+1, add);
    }
};
fill(cnt, cnt+sz, 0);
for(int i : edge[v]){
    dfs(i, v, 0, 0);    // 計算完當前子樹的距離與前面窮舉過的距離加進答案
    dfs(i, v, 0, 1);    // 把當前子樹的距離存進去 cnt 
}

每次選一個節點 \(v\) 計算經過他且長度為 \(k\) 的路徑
再把節點 \(v\) 要怎麼選會是最好的 ?

每次選節點 \(v\) 計算長度為 \(k\) 的路徑複雜度最差為 \(O(n)\)
如果選重心?

回想一下重心剖分的複雜度計算

\(T(n)=\sum T(s_i) + O(n)\)

每次會跑過當前連通塊所有節點，找到重心之後把重心拔掉
再繼續遞迴下去

Tree Hash

根據樹的形狀把整棵樹 Hash 成一個值。
進而可以 O(1) 判斷兩棵樹是否為同構

isomorphism

同構圖的定義為給定兩張圖其節點數量相同，且在兩張圖重新編號後能夠使得任兩個點對其連邊狀況相同

上兩張圖為同構圖，把左邊那張編號為 3, 4 的節點交換編號後，其任一點對連邊狀況相同

Rooted Tree Hash

給定兩棵有根樹，判斷是否為同構的有根樹

以上為同構有根樹，每個節點的子節點可以重新排列順序後相同

作法

rolling hash on tree

hash(u) = \(\sum\) hash\((v)\times p^i\) % mod

1. 算出每個子樹 \(v\) 的 hash 值
2. 把所有子樹 \(v\) 的 hash 值排序
3. 依序把每個子樹 \(v\) 的 hash 值加入計算

*葉節點的 hash 值為 1

1. 算出每個子樹的 hash 值
2. 把所有子樹的 hash 值排序
3. 依序把每個子樹的 hash 值加入計算

ll dfs(int u){
    vector<ll> h;
    subtree_sz[u] = 1;
    for(ll child : edge[u]){
        h.push_back(dfs(child));
        subtree_sz[u] += subtree_sz[child];
    }
    sort(h.begin(), h.end());
    ll ret = subtree_sz[u];
    for(ll v : h){
        ret = (ret * base + v) % MOD;
    }
    return ret;
}

如果過不了就多拿幾個參數 hash，反正通常都在亂做

複雜度

每個節點只遍歷一次，每次只排序自己的子節點 hash 值

\(O(NlgN)\)

2020 ICPC Taipei region –- Problem G. Graph Cards

判斷有幾種不同構的水母圖 (簡單環 + 環上點連出去樹 )

• \(\sum n\le 10^6\)

作法

先找環
相信大家都會做 ?

作法

把環上連出去的樹分別去做 hash
把所有環上的每棵樹縮點成整棵樹的 hash 值

題目轉換等價於求 幾種不同構的環狀序列

幾種不同構的環狀序列 ?

minimum rotation !

轉一下序列，把序列變成最小字典序為開頭
即可比較兩個環狀序列是否相同

模板 minimum rotation 可以 \(O(N)\) 做到求出最小字典序旋轉
函數會回傳要把哪個位置當成開頭
內建函數 rotate() 可以幫你旋轉不用自己轉

無根樹判斷同構?

由於一棵樹的重心最多只有兩個，因此我們可以直接用重心當根
去做有根樹 hash

判斷兩棵樹是否為同構只需要判斷兩個重心的 hash 值是否相同即可

Question Time and Practice

Homework Link

提交期限到 1/13 23:59 截止

本學期課程結束 ! 相信大家都收穫滿滿 ?

希望大家對於之後演算法設計、程式實作、面試等等都會有幫助
並不是只是一個三學分的課而已

之後在寫程式前都能先好好分析複雜度、想想學過的演算法是否可以用上

祝大家聖誕節快樂

期末考 1/6 6:30 大家記得來考 : )

考試內容：練習賽題目、這幾周上課內容