# 樹論 Author:guagua0407 --- ## 主題 - 樹的簡介 - 最小生成樹 - Euler Tour(樹壓平) - 樹 DP - LCA and 倍增法 --- ## 樹的簡介 ---- ### 樹是什麼 **樹(Tree)** 即為一張有 $N$ 個點以及 $N-1$ 條邊的連通圖 ( $N \geq 1$ )  ---- ### 名詞定義 - **節點(Node)** 圖上和樹上的點都叫做節點 - **父節點 (Parent)** 一個節點的父節點會和這個點連接且在這個點的上面 - **子節點 (Child)** 若A的父節點為B，則B的子節點為A - **樹根 (Root)** 最上面的那個節點，根沒有父節點，樹上所有節點都能當成根 ---- ### 名詞定義 - **葉子 (Leaf)** 沒有子節點的節點 - **祖先 (Ancestor)** 某節點的父親/父親的父親/..都是此節點的祖先 - **子孫 (Descendant)** 某節點的小孩/小孩的小孩/..都是此節點的子孫 - **深度 (Depth)** 一個節點離樹根的深度即為深度 - **森林 (Forest)** 森林是由很多顆樹組成的 ---- ### 性質 - 樹上沒有環 - 任兩點之間有且只會有一條路徑 ---- ### 實作 用 vector 存 ```cpp vector<int> adj[n]; for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); } ``` --- ## 最小生成樹 ---- ### 定義 一張帶權圖的最小生成樹(Minimum Spanning Tree)是一個 $N-1$ 條邊的集合使得 1. 圖上的 $N$ 個點和這 $N-1$ 條邊可以組成一顆樹 2. 這個樹的邊權總和最小  ---- ### 性質一：Cycle Property 若 $C$ 是圖上的一個環且 $e$ 是此環上唯一權重最大的一條邊，則 $e$ 不會是最小生成樹的一部分 ---- ### 證明 反證法！ 設 $e$ 在最小生成樹裡 把 $e$ 拿走的話樹會裂成兩顆樹，但 $C$ 之中會有一條邊可以把這兩顆樹給接回來且權重比 $e$ 小，矛盾！ 想想看，如果權重最大的邊不唯一怎麼辦？ ---- ### 性質二：Cut Property Cut是什麼？ 一張圖的割(Cut)即為一個邊的集合使得拔掉這些邊之後會讓這張圖不連通  ---- ### Cut Property 若 $C$ 是圖上的一個割且 $e$ 是此割上唯一權重最小的一條邊，則 $e$ 會是最小生成樹的一部分 ---- ### 證明 反證法again！ 設 $e$ 不在最小生成樹裡 把 $e$ 加進樹後會形成一個環，就可以在 $C$ 之中選一條權重比 $e$ 大的邊拔掉，保持連通且權重還更小，矛盾！ 想想看，如果權重最小的邊不唯一怎麼辦？ ---- ### Kruskal's 把邊依權重由小到大試著加入途中，如果不會形成環則可以 ---- ### 證明 Case 1：加入之後會形成環 - 這條邊會是環上邊權最大的邊，由 Cycle Property 可知這條邊不會是 MST 的一部分 Case 2：加入之後不會形成環 - 這條邊會成為橋並連接左右兩棵樹，這條邊會是 Cut 上邊權最小的邊，所以根據 Cut Property 他不會是 MST 的一部分 ---- ### 實作 DSU 複雜度：$O(|E|\alpha(|V|))$ ```cpp sort(all(Edges)); int ans=0; for(auto e:Edges){ if(DSU.unite(e.a,e.b)){ ans+=e.w; } } return ans; ``` ---- ### 來做做看題目吧 [道路工程](https://neoj.sprout.tw/problem/735/) 題目：給你一張圖，至少要刪除幾條邊才能使得最小生成樹唯一？ ---- :::spoiler Hint 1 什麼情況下最小生成樹會不唯一？ ::: :::spoiler Hint 2 由 Cut Property 可知若一個割內有多條邊權最小的邊則最小生成樹不唯一。 ::: :::spoiler Hint 3 如果先找好一顆最小生成樹再按照某個順序把其他邊加入看看呢？ ::: :::spoiler 解答 我們現在先隨便找一顆最小生成樹，接著將所有的邊按照邊權排序，若邊權相同則將不在目前的最小生成樹裡的邊排在前面。 現在我們假設還沒有邊被加入生成樹內，將這些邊一個一個試著加入看看。 Case 1： 此邊在原本的最小生成樹內，則直接加入。 Case 2： 此邊不在原本的最小生成樹內，則檢查他連接的兩個點是否已經在同一個連通塊內。如果不是的話我們可以知道還有一個在原本的最小生成樹內的邊和目前的邊有相同的邊權，且這兩個邊都是某一個 Cut 內邊權最小的邊，所以這條邊一定要被拔掉最小生成樹才會唯一。 ::: ---- 習題： [CSES-Road Reparation](https://cses.fi/problemset/task/1675) [CF-Minimum spanning tree for each edge](https://codeforces.com/problemset/problem/609/E) [NEOJ-石油](https://neoj.sprout.tw/problem/736/) [USACO Guide](https://usaco.guide/gold/mst?lang=cpp) --- ## Euler Tour(樹壓平) ---- 將進入子樹和離開子樹的時候的 dfs order 存起來，可以做很多事情。 ---- ### 經典題目 [CSES-Subtree Queries](https://cses.fi/problemset/task/1137/) 題目：給一棵有點權的樹，有兩種操作 1.修改某個點權 2.問某個子樹的點權總和 $N,Q \leq 2*10^5$ ---- 不能暴力改，怎麼辦？ ---- 記錄所有點的進入和離開的 dfs order 為 $L[v],R[v]$  ---- 接著將所有點照 dfs order 排序 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | ---- | ---- | --- | ---- | --- | --- | --- | | 5 | 1 | 2 | 6 | 3 | 4 | 7 | 就發現每個子樹都變成一個區間了！ 更酷的是，**$L[v]~R[v]$ 正好就是 $v$ 的子樹的範圍！** ---- 這樣就變成一個單點修改，區間查詢的問題了！ 複雜度：$O((N+Q)logN)$ ---- 習題： [CSES-Path Queries](https://cses.fi/problemset/task/1138) [USACO-Milk Visit](http://www.usaco.org/index.php?page=viewproblem2&cpid=970) [USACO Guide](https://usaco.guide/gold/tree-euler?lang=cpp) --- ## 樹DP ---- 樹上的動態規劃(DP) ---- ### 經典題目 [CSES-Tree Matching](https://cses.fi/problemset/task/1130) 題目：給一棵樹，找出最大的 Matching (邊的集合使得兩兩邊不共點) $N \leq 2*10^5$ ---- ### DP狀態 $dp1[v]=$ 如果選一條 $v$ 到他的小孩的邊，$v$ 的子樹的答案 $dp2[v]=$ 如果不選 $v$ 到他的小孩的邊，$v$ 的子樹的答案 ---- ### DP轉移 先看 $dp2[v]$ 會發現因為都不會取到小孩的邊所以就直接看每個小孩的兩個 $dp$ 值選比較大的加起來而已 $dp2[v]=\displaystyle\sum_{u\in child(v)} max(dp1[u],dp2[u])$ ---- ### DP轉移 再看 $dp1[v]$ 會發現可以枚舉要取哪條邊，並且假設取了到 $u$ 的邊則 $u$ 的答案就只能取 $dp2[u]+1$ 而不是剛取的 $max(dp1[u],dp2[u])$，但也很好處理 $dp1[v]=$ $\displaystyle\max_{u \in child(v)}(dp2[u]+1+ dp2[v]-max(dp1[u],dp2[u]))$ ---- ### 換根 dp ---- ### 經典題目 [CSES-Tree Distance I](https://cses.fi/problemset/task/1132) 題目：給你一棵樹，問你對於每個點離他最遠的點跟他的距離是多少？ $N \leq 2*10^5$ ---- 照剛剛的方法，$dp[v]$ 設為子樹的答案？ 離 $v$ 最遠的點不一定會在 $v$ 的子樹裡，燒雞了 怎麼辦？ ---- ### 兩個dp 假設 $dp1[v]$ 是 $v$ 離他的子樹裡的點最長的距離 $dp2[v]$ 是 $v$ 離他的子樹以外的點最長的距離 $v$ 的答案就是 $max(dp1[v],dp2[v])$ ---- ### 轉移 $dp1[v]$ 顯然很好做，他只是 $\displaystyle\max_{u \in child(v)} (dp1[u]+1)$ 而已，DFS 一次就可以算了 ---- $dp2[c]=max(dp2[v]+1,dp1[d]+2)$ 這裡的 $c$ 和 $d$ 分別是 $v$ 的兩個相異小孩 ---- 你可能會想說這樣怎麼做？其實最大的 $dp1[d]+2$ 就可能是 $dp1[v]+1$ 不是的狀況是 $dp1[v]+1$ 其實是由 $c$ 所貢獻的所以不能用來轉移給 $c$ ---- 為了避免這種狀況，可以存前兩大的 $dp1[v]$ 然後紀錄是從哪裡轉移來的 這樣如果不幸的最大的 $dp1[v]$ 是由 $c$ 轉移過來的你還有第二大的可以用，這樣就完成了！ ----  ---- ### 習題 [AC-Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p) [AC-Subtree](https://atcoder.jp/contests/dp/tasks/dp_v) [CF-Distance in Tree](https://codeforces.com/contest/161/problem/D) [USACO-Fertilizing Pastures](http://www.usaco.org/index.php?page=viewproblem2&cpid=1306) [USACO Guide](https://usaco.guide/gold/dp-trees?lang=cpp) [USACO Guide](https://usaco.guide/gold/all-roots?lang-cpp) --- ## LCA and 倍增法 ---- 兩個節點的 $LCA$(Lowest Common Ancestor) 即是他們深度最大的共同祖先  ---- ### 經典題目 [CSES-Company Queries II](https://cses.fi/problemset/task/1688) $N,Q \leq 2*10^5$ ---- 怎麼找？ ---- ### 暴力 枚舉所有祖先看第一個一樣的，每找一次會花 $O(N)$ 會變成 $O(NQ)$，吃爆 $TLE$ ---- ### 觀察 假設兩個節點的深度一樣，是不是就只要找往上幾步會走到 $LCA$？ 可以用類似二分搜的方法找 - 兩個節點都往上 $2^k$ 步 - 如果變成一樣的點那就表示超過了，$Ans$ 的第 $k$ 個 $bit$ 要取 $0$，反之取 $1$ - $k$ 減少 $1$，重複上面的步驟 最後找到的 $Ans+1$ 就是要往上幾步會走到 $LCA$ ---- 好喔，所以現在我們需要馬上知道隨便一個點往上 $2^k$ 步會走到哪個點，怎麼辦？ 倍增法！ ---- ### 倍增法 把 $v$ 往上 $2^{k-1}$ 步走到的點叫做 $u$ 那 $v$ 往上 $2^k$ 步是不是其實就是 $u$ 往上 $2^{k-1}$ 步？ 現在我們可以用 $k-1$ 的答案算出 $k$ 的答案了！ 喔，這根本就是 DP 阿 ---- ### 狀態及轉移 設 $up[v][k]$ 等於 $v$ 往上走 $k$ 步會走到的點 $up[v][k]=up[up[v][k-1]][k-1]$ 有 $O(NlogN)$ 個狀態，$O(1)$ 的轉移，總複雜度 $O(NlogN)$！ ---- 回到剛剛的題目，你現在可以解決深度一樣的情況了，那深度不一樣呢？ 又是倍增法！其實因為你有所有 $2$ 的冪次的答案，就可以在 $O(logN)$ 的時間內任意往上 $x$ 步了，要把深度調成一樣的也就很容易了 這樣就完整解決這個題目了！ ---- ### 完整解法 - 用 $O(logN)$ 時間將比較深的節點往上到跟另一個節點深度一樣 - 用類似二分搜的方法由大到小枚舉 $bit$ - 如果兩個節點往上 $2^{bit}$ 步會一樣，$Ans$ 的 $bit$ 是 $0$ 反之 $1$ - 任一節點往上 $Ans+1$ 步即為答案 ---- ### 習題： [CSES-Distance Queries](https://cses.fi/problemset/task/1135) [CSA-Root LCA Queries](https://csacademy.com/contest/archive/task/root-lca-queries) [**AC-Distance Queries on a Tree**](https://atcoder.jp/contests/abc294/tasks/abc294_g) [CSES-Planets Queries II](https://cses.fi/problemset/task/1160) 上面那題還有用到水母圖的概念 [USACO Guide](https://usaco.guide/plat/binary-jump?lang=cpp) --- # 樹論讚讚