--- ###### tags: `2020 師大附中校隊培訓` --- # 樹 ## 2020 師大附中校隊培訓 #### joylintp #### 10.28.2020 --- ## 樹 ## Tree ----  樹(tree): 任兩點之間都相通且沒有環的圖 * 一棵有$n$個節點的樹恰有$n-1$條邊 ----  ### 根節點 ----  ### 葉節點 ----  ### 父節點 ----  ### 子節點 ----  ### 祖先 ----  ### 子代 ----  ### 子樹 ----  ### 層 --- ## 樹直徑 一棵樹當中最遠的兩點間的簡單路徑 ----  ---- #### 作法 1. 選取任意點 $x$ 進行DFS 2. 找到距離 $x$ 最遠的點 $u$ 3. 再從 $u$ 點進行 DFS 4. 找到距離 $u$ 最遠的點 $v$ 5. $u$、$v$ 間的簡單路徑即為樹直徑 ---- #### 實作 ```cpp= #include<bits/stdc++.h> using namespace std; bool vis[100000]; int dis[100000]; vector<int> edge[100000]; void dfs(int rt) { vis[rt] = true; for (int i : edge[rt]) if (!vis[i]) dis[i] = dis[rt] + 1, dfs(i); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; while (cin >> n) { for (int i = 0; i < n; i++) edge[i].clear(); int a, b; for (int i = 0; i < n - 1; i++) cin >> a >> b, edge[a].push_back(b), edge[b].push_back(a); for (int i = 0; i < n; i++) vis[i] = 0, dis[i] = 1e9; dis[0] = 0, dfs(0); int mx = 0, mxn = 0; for (int i = 0; i < n; i++) mx = max(mx, dis[i]); for (int i = 0; i < n; i++) if (dis[i] == mx) mxn = i; for (int i = 0; i < n; i++) vis[i] = 0, dis[i] = 1e9; dis[mxn] = 0, dfs(mxn); mx = 0; for (int i = 0; i < n; i++) mx = max(mx, dis[i]); cout << mx << '\n'; } return 0; } ``` ---- * [b967: 第 4 題 血緣關係（樹直徑）](https://zerojudge.tw/ShowProblem?problemid=b967) * [1211 . 圖論 之 最小生成樹（帶權樹直徑）](https://tioj.ck.tp.edu.tw/problems/1211) --- ## 樹重心 拔除該節點後剩餘子樹的節點數不超過原樹的 $\frac{1}{2}$，該點即為原樹的重心 ----  ---- #### 作法 1. DFS求出以每個節點為根的子樹大小 2. 判斷每個點是否符合條件 ---- #### 實作 ```cpp= #include<bits/stdc++.h> using namespace std; bool vis[100000]; int n, sz[100000], par[100000]; vector<int> edge[100000]; void dfs(int u) { vis[u] = true; sz[u] = 1; for (int i : edge[u]) if (!vis[i]) par[i] = u, dfs(i), sz[u] += sz[i]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; i++) edge[i].clear(), sz[i] = par[i] = 0, vis[i] = false; int a, b; for (int i = 1; i < n; i++) cin >> a >> b, edge[a].push_back(b), edge[b].push_back(a); dfs(0); for (int i = 0; i < n; i++) { int mx = n - sz[i]; for (int j : edge[i]) if (j != par[i]) mx = max(mx, sz[j]); if (mx <= n / 2) { cout << i << '\n'; break; } } } return 0; } ``` ---- * [樹重心](https://neoj.sprout.tw/problem/293/) --- ## 並查集 一種資料結構，它可以支援以下操作： * 詢問某元素隸屬的集合 * 合併兩個集合 ---- 點集合在圖論上可被當成「連通塊」 → 並查集擁有查詢任兩點是否連通的功能 ---- ```cpp= int group[100001]; void init(int n) { for (int i = 1; i <= n; i++) group[i] = i; } int fnd(int a) { if (a == group[a]) return a; return group[a] = fnd(group[a]); } void uni(int a, int b) { int x = fnd(a), y = fnd(b); if (x == y) return; else group[x] = y, sz[y] += sz[x]; } ``` --- ## 最小生成樹 ### Minimum Spanning Tree 無向圖中，一個樹的子圖其包含原圖的所有節點稱為一棵生成樹 其中邊權總和最小的生成樹即為最小生成樹 ---- ### Krsukal’s algorithm 將原圖中連接一部分點的生成樹稱為最小生成子樹： * 一個單獨的點，可以視作一棵最小生成子樹 * 兩棵最小生成子樹連結成一棵最小生成子樹，以兩棵子樹之間權重最小的邊連接，顯然是最好的 * 三棵最小生成子樹連接成一棵最小生成子樹，先連結其中兩棵權重最小的子樹，再連接第三棵，總是比較好 ---- ### 貪心法，從最小權重的邊開始選起 * 若目前權重最小的邊其兩個端點隸屬於不同的集合，則選取該條邊 * 若兩個點隸屬同一集合，也就是兩點間已連通，則不選擇該條邊 複雜度 $O(E(log\ E+\alpha (V))$ ---- ### Prim's algorithm 觀察另一性質：從當前最小生成樹往外連邊權最小的邊必定是好的 * 取任意一點為起點，設為一開始的最小生成樹 * 找樹外與樹最短的邊並與目前的最小生成樹相連 複雜度 $O((V+E)log\ E)$ --- ## 最低共同祖先 ### Lowest Common Ancestor 有根樹上兩節點的最低共同祖先為其祖先的交集中深度最深者 ---- ### 時間戳記，判斷兩節點是否有祖先關係 遍歷有根樹時， 設進入節點 $i$ 的時間為 $in_i$，離開的時間為 $out_i$，可觀察到： * $u$ 是 $v$ 的祖先若且唯若 $in_u \le in_v$ 且 $out_v \le out_u$ ```cpp= void dfs(int rt) { vis[rt] = true, in[rt] = T++; for (int i : edge[rt]) if (!vis[i]) dfs(i); out[rt] = T++; } bool ancestor(int u, int v) { return (in[u] <= in[v] && out[v] <= out[u]); } ``` ---- ### 倍增法，預處理每個節點往上 $2^k$ 層祖先 ```cpp= int ac[k][n]; // 表示節點n第2^k層的祖先 for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) ac[i][j] = ac[i - 1][ac[i - 1][j]]; // 第2^i層的祖先是第2^(i-1)層的祖先的第2^(i-1)層的祖先 ``` 建表複雜度為 $O(kn)$ → 層數不會超過$n$層，複雜度為 $O(n\ log\ n)$ ---- ### 查詢 $u$、$v$ 的 LCA 特殊情況： * 若 $u$ 為 $v$ 的祖先，則 $u$、$v$ 的 LCA 為 $u$ * 若 $v$ 為 $u$ 的祖先，則 $u$、$v$ 的 LCA 為 $v$ ---- ### 查詢 $u$、$v$ 的 LCA ### 二分搜 若 $u$ 點的第 $i$ 層祖先是 $v$ 的祖先，則 $u$ 點的第 $i+1$ 層祖先也是 $v$ 的祖先 ```cpp= int LCA(int a, int b) { if (ancestor(a, b)) return a; if (ancestor(b, a)) return b; for (int i = k; i >= 0; i--) if (!ancestor(ac[i][a], b)) a = ac[i][a]; // 提高下界，把a設為第2^i層的祖先 return ac[0][a]; } ``` 時間複雜度 $O(log\ n)$