<style> .reveal .slides { text-align: left; font-size:30px; } </style> ## Graph Problem Misc - Constraint Difference System - Centroid Decomposition - Tree Hash - Round-square tree --- ## 差分約束系統 ### Constraint Difference System 是求解關於一組不等式之方法。 $n$ 個變數和 $m$ 個約束條件組成 其中每個約束條件形如 ${ x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}$ 則稱其為差分約束系統。 ---- ## 例子 ${x_{1}-x_{2}\leq 8}$ ${x_{1}-x_{3}\leq 2}$ $\to x_{1}=3, x_{2}=-5, x_{3}=1$ ${x_{1}-x_{2}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$ $\to$ 無解 <div style="position: absolute; right: 10%; top:0%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 作法 轉成圖論問題 對於所有 $x_{j}-x_{i}\leq k$ 連接一條邊 $(i, j)$，權重為 $k$ 最後再設置一個起點 $s$，連向所有邊邊權為 $0$ 從起點 $s$，跑 Bellman Ford/SPFA ， 若出現負環則代表這組不等式無解 ---- ## 建圖 ${x_{1}-x_{2}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$  ---- ## 結果 跑完 Bellman Ford/SPFA 如果發現有負環，則此組不等式無解 否則所有點到起點的距離為其中一組解 ---- ## 變化 | 限制 | 建邊 | | -------- | -------- | | $x_{j}-x_{i}\leq k$ | addEdge($i, j, k$) | | $x_{j}-x_{i}\geq k$ | addEdge($j, i, -k$) | | $x_{j} = x_{i}$ | addEdge($i, j, 0$), addEdge($j, i, 0) | ---- ## 區間問題轉換 給 $n$ 個區間 $[l_i, r_i]$ 以及 $c_i$ 要構造出一個序列 $\forall i\in [1, n]$ 滿足區間 $[l_i, r_i]$ 內的總和至少為 $c_i$， 構造出總和最小的序列。 ---- ## 轉換為前綴和處理 $[l_i, r_i]$ 至少為 $c_i$ 等價於前綴和 $pre_r$ - $pre_{l-1}$ 至少為 $c_i$ ---- 等價於前綴和 $pre_r - pre_{l-1}$ 至少為 $c_i$ $\to pre_r - pre_{l-1}\ge c_i$ 把序列上每個位置當成節點，即可轉換為差分約束問題 ! --- ## 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  ---- 找到<span style = "color:red;">樹重心 </span>  ---- 把樹重心從塗上移除，剩下的子圖分別去找各自的樹重心  ---- 找到子圖各自的<span style = "color:orange;">樹重心 </span>  ---- 把樹重心移除，剩下的子圖分別去找個字的樹重心  ---- 找到各自的<span style = "color:green;">樹重心 </span>  ---- ## 複雜度 每次把圖從重心分割，每個子圖最大為原本的一半 最多遞迴 $\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 到紅色最短   答案會是 ```txt 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 ```cpp= 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 陣列裡 ```cpp= 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 Isomorphism 給定兩棵有根樹，判斷是否為同構的有根樹   以上為同構有根樹，每個節點的子節點可以重新排列順序後相同 ---- ## radix-sort style compression 給每種有根樹一個 unique id， 把每個兒子的 id 排序用 vector 存進 map 中維護 ```cpp map<vector<int>, int> id; int dfs(int x, int f){ vector<int> sub; for (int v : edge[x]){ if (v != f) sub.push_back(dfs(v, x)); } sort(sub.begin(), sub.end()); if (!id.count(sub)) id[sub] = id.size(); return id[sub]; } ``` ---- ## 複雜度 每個節點只遍歷一次， 每次只排序自己的子節點 id 值並存進 map 中 $O(N\log N)$ --- ## 圓方樹 ### Block forest, Round-square tree 一種將圖變成樹的方法，使得一些圖上問題能夠在 $O(\log n)$ 解決 ---- ## 例題 --- CSES 1705. Forbidden Cities 給定一張無向圖，$q$ 筆詢問 每筆詢問為是否存在一條路徑使得點 $a$ 到點 $b$ 不經過點 $c$ $1\le n, m, q\le 10^5$ <span>會發現題目即為判斷點 c 是否為 a-b 路徑上的關節點<!-- .element: class="fragment" data-fragment-index="1" --></span> ---- ## 建樹 而要判斷路徑上的問題，我們可以用 BCC 縮點，把每個 BCC 變成一個點 對於每個 BCC 與相連的關節點建邊   如此一來，建出來的圖會變成一顆樹，總共 $b+c$ 個點 $b$ 為 BCC 數量，$c$ 為關節點數量 ---- ## 實作 找出所有關節點，以及把非關節點的點都縮點成 BCC 的編號 實作上方便，我們可以把 BCC 的編號從 n+1 開始 ```cpp= int num[MXN]; vector<int> edge[MXN]; // new graph vector<vector<int>> bcc = BCC.solve(); for(auto i : bcc){ for(int j : i) num[j]++; } for(int i = 0; i < bcc.size(); i++){ auto b = bcc[i]; if(b.size() == 2){//bridge edge[b[0]].push_back(edge[b[1]]); edge[b[1]].push_back(edge[b[2]]); bln[b[0]] = b[0]; bln[b[1]] = b[1]; } else{ for(int j : b){// set bcc index to n+1+i if(num[j] > 1){// articulation points edge[num[j]].push_back(n+1+i); edge[n+1+i].push_back(num[j]); bln[num[j]] = num[j]; } else{ bln[j] = n+1+i; // set node to bcc index } } } } ``` ---- 建出樹之後，即可進行樹上操作 如這題是判斷點 $c$ 是否在點 $a-b$ 的路徑上 可以使用 LCA 維護 或者其他需要修改的題目也可以搭配樹鏈剖分進行動態操作