現(xiàn)詳解)
1. 樹的重心概念與算法解析樹的重心是圖論中一個(gè)非常重要的概念特別是在處理樹形結(jié)構(gòu)的算法問題時(shí)。簡(jiǎn)單來說樹的重心是指樹中這樣一個(gè)節(jié)點(diǎn)當(dāng)我們將它從樹中刪除后剩下的各個(gè)連通塊中節(jié)點(diǎn)數(shù)的最大值最小。這個(gè)定義可能聽起來有些抽象讓我們用一個(gè)實(shí)際的例子來說明。假設(shè)我們有一棵樹它有n個(gè)節(jié)點(diǎn)。對(duì)于樹中的每一個(gè)節(jié)點(diǎn)我們都可以計(jì)算刪除它后得到的各個(gè)子樹的大小即節(jié)點(diǎn)數(shù)量。樹的重心就是使得這些子樹大小的最大值最小的那個(gè)節(jié)點(diǎn)。值得注意的是一棵樹可能有一個(gè)或兩個(gè)重心。計(jì)算樹的重心的算法通常采用深度優(yōu)先搜索DFS的方式。算法的核心思想是對(duì)于每個(gè)節(jié)點(diǎn)我們計(jì)算它所有子樹的大小同時(shí)記錄下刪除該節(jié)點(diǎn)后最大子樹的大小。最后我們選擇使得這個(gè)最大值最小的節(jié)點(diǎn)作為樹的重心。int dfs(int u) { st[u] true; // 標(biāo)記已訪問 int size 1, max_size 0; // size表示以u(píng)為根的子樹大小 for (int i h[u]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { int s dfs(j); max_size max(max_size, s); size s; } } max_size max(max_size, n - size); if (max_size ans_size) { ans_size max_size; ans_node u; } return size; }注意在實(shí)際實(shí)現(xiàn)時(shí)需要初始化ans_size為一個(gè)足夠大的數(shù)比如nans_node為-1n為樹的節(jié)點(diǎn)總數(shù)。2. 加邊函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)在圖論算法中加邊函數(shù)是最基礎(chǔ)也是最重要的操作之一。特別是在處理樹或圖的結(jié)構(gòu)時(shí)如何高效地實(shí)現(xiàn)加邊操作直接影響到整個(gè)算法的效率。在AcWing的題目中通常會(huì)使用鄰接表來存儲(chǔ)圖結(jié)構(gòu)因此我們需要設(shè)計(jì)一個(gè)高效的加邊函數(shù)。鄰接表加邊的標(biāo)準(zhǔn)實(shí)現(xiàn)通常包括以下幾個(gè)部分邊的存儲(chǔ)使用數(shù)組來存儲(chǔ)邊的信息邊的索引使用頭指針數(shù)組來記錄每個(gè)節(jié)點(diǎn)的第一條邊邊的鏈接通過next指針將同一個(gè)節(jié)點(diǎn)的邊連接起來const int N 100010, M N * 2; int h[N], e[M], ne[M], idx; void add(int a, int b) { e[idx] b; ne[idx] h[a]; h[a] idx; }這個(gè)加邊函數(shù)的實(shí)現(xiàn)非常簡(jiǎn)潔高效。它使用了三個(gè)數(shù)組e數(shù)組存儲(chǔ)邊的終點(diǎn)ne數(shù)組存儲(chǔ)下一條邊的索引h數(shù)組存儲(chǔ)每個(gè)節(jié)點(diǎn)的第一條邊的索引idx是當(dāng)前可用的邊索引提示在使用前需要初始化h數(shù)組為-1memset(h, -1, sizeof h)表示初始時(shí)每個(gè)節(jié)點(diǎn)都沒有邊。3. 樹的重心算法實(shí)現(xiàn)細(xì)節(jié)理解了樹的重心概念和加邊函數(shù)后我們可以來看完整的樹的重心算法實(shí)現(xiàn)。這個(gè)算法通常分為以下幾個(gè)步驟圖的構(gòu)建使用加邊函數(shù)構(gòu)建樹的鄰接表表示DFS遍歷從任意節(jié)點(diǎn)開始進(jìn)行深度優(yōu)先搜索子樹大小計(jì)算在DFS過程中計(jì)算每個(gè)子樹的大小重心判斷比較并記錄可能的重心節(jié)點(diǎn)#include iostream #include cstring using namespace std; const int N 100010, M N * 2; int h[N], e[M], ne[M], idx; bool st[N]; int n, ans_node, ans_size N; void add(int a, int b) { e[idx] b; ne[idx] h[a]; h[a] idx; } int dfs(int u) { st[u] true; int size 1, max_size 0; for (int i h[u]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { int s dfs(j); max_size max(max_size, s); size s; } } max_size max(max_size, n - size); if (max_size ans_size) { ans_size max_size; ans_node u; } return size; } int main() { memset(h, -1, sizeof h); cin n; for (int i 0; i n - 1; i) { int a, b; cin a b; add(a, b), add(b, a); } dfs(1); cout ans_node endl; return 0; }這個(gè)實(shí)現(xiàn)有幾個(gè)關(guān)鍵點(diǎn)需要注意樹是無向圖所以每條邊需要添加兩次a→b和b→aDFS的起點(diǎn)可以是任意節(jié)點(diǎn)因?yàn)闃涫沁B通的ans_size初始化為N節(jié)點(diǎn)總數(shù)的上限確保第一次比較能成功使用st數(shù)組來避免重復(fù)訪問4. 算法的時(shí)間復(fù)雜度分析理解算法的時(shí)間復(fù)雜度對(duì)于評(píng)估算法效率非常重要。讓我們來分析樹的重心算法的時(shí)間復(fù)雜度。加邊操作每次add操作是O(1)的對(duì)于n個(gè)節(jié)點(diǎn)的樹有n-1條邊每條邊添加兩次所以總加邊時(shí)間是O(n)DFS遍歷每個(gè)節(jié)點(diǎn)和每條邊都只被訪問一次所以時(shí)間復(fù)雜度是O(n)其他操作初始化、輸入輸出等都是O(n)或O(1)的因此整個(gè)算法的時(shí)間復(fù)雜度是O(n)這是非常高效的可以處理規(guī)模很大的樹比如n1e5。空間復(fù)雜度方面鄰接表存儲(chǔ)需要O(n)的空間st數(shù)組需要O(n)的空間遞歸棧在最壞情況下可能需要O(n)的空間所以總的空間復(fù)雜度也是O(n)。5. 常見問題與調(diào)試技巧在實(shí)際實(shí)現(xiàn)樹的重心算法時(shí)可能會(huì)遇到各種問題。下面列出一些常見問題及其解決方法無限遞歸問題現(xiàn)象程序運(yùn)行后卡死或棧溢出原因忘記標(biāo)記已訪問節(jié)點(diǎn)導(dǎo)致節(jié)點(diǎn)被重復(fù)訪問解決確保在dfs開始時(shí)標(biāo)記st[u]true錯(cuò)誤的重心結(jié)果現(xiàn)象輸出的重心節(jié)點(diǎn)不正確原因可能沒有考慮父節(jié)點(diǎn)方向的子樹大小解決確保計(jì)算max_size時(shí)包含了n-size這一項(xiàng)邊添加不全現(xiàn)象程序無法遍歷整棵樹原因忘記無向圖需要添加雙向邊解決確保對(duì)于每條邊a-b都執(zhí)行add(a,b)和add(b,a)初始化問題現(xiàn)象程序行為異常原因h數(shù)組沒有初始化為-1或ans_size沒有初始化為足夠大的值解決在main函數(shù)開始處正確初始化所有數(shù)組和變量調(diào)試技巧對(duì)于小規(guī)模的樹n5-10可以手工計(jì)算重心并與程序輸出對(duì)比打印中間結(jié)果如每個(gè)節(jié)點(diǎn)的size和max_size值使用圖形化工具繪制樹結(jié)構(gòu)直觀理解算法過程6. 算法應(yīng)用場(chǎng)景與擴(kuò)展樹的重心算法在實(shí)際中有很多應(yīng)用場(chǎng)景下面列舉幾個(gè)典型的應(yīng)用樹的分解重心分解是解決樹上路徑問題的有力工具通過遞歸地找到重心并分解樹可以高效解決許多問題動(dòng)態(tài)樹維護(hù)在一些需要?jiǎng)討B(tài)維護(hù)樹結(jié)構(gòu)的問題中重心可以幫助保持樹的平衡網(wǎng)絡(luò)設(shè)計(jì)在計(jì)算機(jī)網(wǎng)絡(luò)中選擇重心作為服務(wù)器位置可以最小化最遠(yuǎn)客戶端的距離游戲AI在一些基于樹形結(jié)構(gòu)的游戲AI中重心可以幫助確定關(guān)鍵位置算法擴(kuò)展可以修改算法找出所有重心一棵樹最多有兩個(gè)重心可以記錄每個(gè)節(jié)點(diǎn)作為重心時(shí)的最大子樹大小可以結(jié)合其他樹算法如直徑計(jì)算、最近公共祖先等7. 性能優(yōu)化與變種實(shí)現(xiàn)雖然標(biāo)準(zhǔn)實(shí)現(xiàn)已經(jīng)很高效但在某些特殊情況下還可以進(jìn)一步優(yōu)化迭代式DFS對(duì)于非常大的樹遞歸可能導(dǎo)致棧溢出可以改為迭代實(shí)現(xiàn)int dfs_iterative(int u) { stackpairint, bool stk; stk.push({u, false}); int size 0; while (!stk.empty()) { auto [node, visited] stk.top(); stk.pop(); if (visited) { int max_size 0, total 1; // 處理子節(jié)點(diǎn)結(jié)果 // ... max_size max(max_size, n - total); if (max_size ans_size) { ans_size max_size; ans_node node; } size total; } else { st[node] true; stk.push({node, true}); for (int i h[node]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { stk.push({j, false}); } } } } return size; }并行計(jì)算對(duì)于特別大的樹可以考慮并行計(jì)算子樹的大小動(dòng)態(tài)樹處理如果需要處理動(dòng)態(tài)變化的樹可以研究專門的數(shù)據(jù)結(jié)構(gòu)來維護(hù)樹的重心8. 實(shí)際案例分析讓我們通過一個(gè)具體的例子來演示算法的工作過程?？紤]如下樹結(jié)構(gòu)1 | \ 2 3 | \ 4 5節(jié)點(diǎn)連接情況 1-2, 1-3, 3-4, 3-5算法執(zhí)行過程從節(jié)點(diǎn)1開始DFS訪問節(jié)點(diǎn)1遞歸訪問節(jié)點(diǎn)2和3節(jié)點(diǎn)2是葉子節(jié)點(diǎn)返回size1節(jié)點(diǎn)3遞歸訪問節(jié)點(diǎn)4和5節(jié)點(diǎn)4和5都是葉子節(jié)點(diǎn)各返回size1節(jié)點(diǎn)3得到子樹大小4和5都是1max_size1size1113節(jié)點(diǎn)1得到子樹大小2返回13返回3max_sizemax(1,3)3 還要考慮父節(jié)點(diǎn)方向n-size5-41所以max_sizemax(3,1)3比較并記錄當(dāng)前最小max_size繼續(xù)處理其他節(jié)點(diǎn)...最終會(huì)發(fā)現(xiàn)節(jié)點(diǎn)1和節(jié)點(diǎn)3的max_size都是3而節(jié)點(diǎn)3的max_size是2刪除3后最大連通塊是1-2-3-5或1-2-3-4大小都是3實(shí)際上節(jié)點(diǎn)1和3都是重心。9. 與其他圖算法的比較樹的重心算法與一些其他常見的圖算法有著有趣的聯(lián)系和區(qū)別與樹直徑算法的比較直徑關(guān)注樹中最長(zhǎng)路徑重心關(guān)注平衡性有趣的是樹的直徑的中點(diǎn)往往就是或接近重心與中心點(diǎn)的比較中心點(diǎn)通常指距離所有節(jié)點(diǎn)最遠(yuǎn)的距離最小的點(diǎn)重心與中心點(diǎn)在樹中通常是同一個(gè)點(diǎn)或相鄰的點(diǎn)與割點(diǎn)的比較割點(diǎn)是刪除后增加連通分量數(shù)的點(diǎn)重心不一定是割點(diǎn)除非樹有特定結(jié)構(gòu)但尋找割點(diǎn)的算法與重心算法有相似之處理解這些算法的關(guān)系可以幫助我們更好地選擇和應(yīng)用合適的算法解決問題。10. 編程競(jìng)賽中的應(yīng)用技巧在編程競(jìng)賽中樹的重心相關(guān)問題有一些常見的解題技巧模板準(zhǔn)備事先準(zhǔn)備好加邊函數(shù)和重心算法的模板可以節(jié)省比賽時(shí)間問題轉(zhuǎn)化很多問題看似與重心無關(guān)但可以轉(zhuǎn)化為重心問題如尋找最優(yōu)位置放置設(shè)施最小化最遠(yuǎn)服務(wù)距離樹的平衡分割組合應(yīng)用將重心算法與其他算法結(jié)合使用如重心分解后應(yīng)用線段樹結(jié)合動(dòng)態(tài)規(guī)劃統(tǒng)計(jì)信息與并查集結(jié)合處理連通性邊界處理特別注意n1和n2等小規(guī)模情況的處理調(diào)試方法先在小樹上手動(dòng)驗(yàn)證打印關(guān)鍵變量的中間值比較不同起點(diǎn)的結(jié)果在比賽中遇到樹的問題時(shí)考慮重心往往能提供獨(dú)特的解題視角特別是當(dāng)問題與樹的平衡性或最值性相關(guān)時(shí)。 樹的重心算法與DFS實(shí)現(xiàn)詳解
1. 樹的重心概念與算法解析樹的重心是圖論中一個(gè)非常重要的概念特別是在處理樹形結(jié)構(gòu)的算法問題時(shí)。簡(jiǎn)單來說樹的重心是指樹中這樣一個(gè)節(jié)點(diǎn)當(dāng)我們將它從樹中刪除后剩下的各個(gè)連通塊中節(jié)點(diǎn)數(shù)的最大值最小。這個(gè)定義可能聽起來有些抽象讓我們用一個(gè)實(shí)際的例子來說明。假設(shè)我們有一棵樹它有n個(gè)節(jié)點(diǎn)。對(duì)于樹中的每一個(gè)節(jié)點(diǎn)我們都可以計(jì)算刪除它后得到的各個(gè)子樹的大小即節(jié)點(diǎn)數(shù)量。樹的重心就是使得這些子樹大小的最大值最小的那個(gè)節(jié)點(diǎn)。值得注意的是一棵樹可能有一個(gè)或兩個(gè)重心。計(jì)算樹的重心的算法通常采用深度優(yōu)先搜索DFS的方式。算法的核心思想是對(duì)于每個(gè)節(jié)點(diǎn)我們計(jì)算它所有子樹的大小同時(shí)記錄下刪除該節(jié)點(diǎn)后最大子樹的大小。最后我們選擇使得這個(gè)最大值最小的節(jié)點(diǎn)作為樹的重心。int dfs(int u) { st[u] true; // 標(biāo)記已訪問 int size 1, max_size 0; // size表示以u(píng)為根的子樹大小 for (int i h[u]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { int s dfs(j); max_size max(max_size, s); size s; } } max_size max(max_size, n - size); if (max_size ans_size) { ans_size max_size; ans_node u; } return size; }注意在實(shí)際實(shí)現(xiàn)時(shí)需要初始化ans_size為一個(gè)足夠大的數(shù)比如nans_node為-1n為樹的節(jié)點(diǎn)總數(shù)。2. 加邊函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)在圖論算法中加邊函數(shù)是最基礎(chǔ)也是最重要的操作之一。特別是在處理樹或圖的結(jié)構(gòu)時(shí)如何高效地實(shí)現(xiàn)加邊操作直接影響到整個(gè)算法的效率。在AcWing的題目中通常會(huì)使用鄰接表來存儲(chǔ)圖結(jié)構(gòu)因此我們需要設(shè)計(jì)一個(gè)高效的加邊函數(shù)。鄰接表加邊的標(biāo)準(zhǔn)實(shí)現(xiàn)通常包括以下幾個(gè)部分邊的存儲(chǔ)使用數(shù)組來存儲(chǔ)邊的信息邊的索引使用頭指針數(shù)組來記錄每個(gè)節(jié)點(diǎn)的第一條邊邊的鏈接通過next指針將同一個(gè)節(jié)點(diǎn)的邊連接起來const int N 100010, M N * 2; int h[N], e[M], ne[M], idx; void add(int a, int b) { e[idx] b; ne[idx] h[a]; h[a] idx; }這個(gè)加邊函數(shù)的實(shí)現(xiàn)非常簡(jiǎn)潔高效。它使用了三個(gè)數(shù)組e數(shù)組存儲(chǔ)邊的終點(diǎn)ne數(shù)組存儲(chǔ)下一條邊的索引h數(shù)組存儲(chǔ)每個(gè)節(jié)點(diǎn)的第一條邊的索引idx是當(dāng)前可用的邊索引提示在使用前需要初始化h數(shù)組為-1memset(h, -1, sizeof h)表示初始時(shí)每個(gè)節(jié)點(diǎn)都沒有邊。3. 樹的重心算法實(shí)現(xiàn)細(xì)節(jié)理解了樹的重心概念和加邊函數(shù)后我們可以來看完整的樹的重心算法實(shí)現(xiàn)。這個(gè)算法通常分為以下幾個(gè)步驟圖的構(gòu)建使用加邊函數(shù)構(gòu)建樹的鄰接表表示DFS遍歷從任意節(jié)點(diǎn)開始進(jìn)行深度優(yōu)先搜索子樹大小計(jì)算在DFS過程中計(jì)算每個(gè)子樹的大小重心判斷比較并記錄可能的重心節(jié)點(diǎn)#include iostream #include cstring using namespace std; const int N 100010, M N * 2; int h[N], e[M], ne[M], idx; bool st[N]; int n, ans_node, ans_size N; void add(int a, int b) { e[idx] b; ne[idx] h[a]; h[a] idx; } int dfs(int u) { st[u] true; int size 1, max_size 0; for (int i h[u]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { int s dfs(j); max_size max(max_size, s); size s; } } max_size max(max_size, n - size); if (max_size ans_size) { ans_size max_size; ans_node u; } return size; } int main() { memset(h, -1, sizeof h); cin n; for (int i 0; i n - 1; i) { int a, b; cin a b; add(a, b), add(b, a); } dfs(1); cout ans_node endl; return 0; }這個(gè)實(shí)現(xiàn)有幾個(gè)關(guān)鍵點(diǎn)需要注意樹是無向圖所以每條邊需要添加兩次a→b和b→aDFS的起點(diǎn)可以是任意節(jié)點(diǎn)因?yàn)闃涫沁B通的ans_size初始化為N節(jié)點(diǎn)總數(shù)的上限確保第一次比較能成功使用st數(shù)組來避免重復(fù)訪問4. 算法的時(shí)間復(fù)雜度分析理解算法的時(shí)間復(fù)雜度對(duì)于評(píng)估算法效率非常重要。讓我們來分析樹的重心算法的時(shí)間復(fù)雜度。加邊操作每次add操作是O(1)的對(duì)于n個(gè)節(jié)點(diǎn)的樹有n-1條邊每條邊添加兩次所以總加邊時(shí)間是O(n)DFS遍歷每個(gè)節(jié)點(diǎn)和每條邊都只被訪問一次所以時(shí)間復(fù)雜度是O(n)其他操作初始化、輸入輸出等都是O(n)或O(1)的因此整個(gè)算法的時(shí)間復(fù)雜度是O(n)這是非常高效的可以處理規(guī)模很大的樹比如n1e5。空間復(fù)雜度方面鄰接表存儲(chǔ)需要O(n)的空間st數(shù)組需要O(n)的空間遞歸棧在最壞情況下可能需要O(n)的空間所以總的空間復(fù)雜度也是O(n)。5. 常見問題與調(diào)試技巧在實(shí)際實(shí)現(xiàn)樹的重心算法時(shí)可能會(huì)遇到各種問題。下面列出一些常見問題及其解決方法無限遞歸問題現(xiàn)象程序運(yùn)行后卡死或棧溢出原因忘記標(biāo)記已訪問節(jié)點(diǎn)導(dǎo)致節(jié)點(diǎn)被重復(fù)訪問解決確保在dfs開始時(shí)標(biāo)記st[u]true錯(cuò)誤的重心結(jié)果現(xiàn)象輸出的重心節(jié)點(diǎn)不正確原因可能沒有考慮父節(jié)點(diǎn)方向的子樹大小解決確保計(jì)算max_size時(shí)包含了n-size這一項(xiàng)邊添加不全現(xiàn)象程序無法遍歷整棵樹原因忘記無向圖需要添加雙向邊解決確保對(duì)于每條邊a-b都執(zhí)行add(a,b)和add(b,a)初始化問題現(xiàn)象程序行為異常原因h數(shù)組沒有初始化為-1或ans_size沒有初始化為足夠大的值解決在main函數(shù)開始處正確初始化所有數(shù)組和變量調(diào)試技巧對(duì)于小規(guī)模的樹n5-10可以手工計(jì)算重心并與程序輸出對(duì)比打印中間結(jié)果如每個(gè)節(jié)點(diǎn)的size和max_size值使用圖形化工具繪制樹結(jié)構(gòu)直觀理解算法過程6. 算法應(yīng)用場(chǎng)景與擴(kuò)展樹的重心算法在實(shí)際中有很多應(yīng)用場(chǎng)景下面列舉幾個(gè)典型的應(yīng)用樹的分解重心分解是解決樹上路徑問題的有力工具通過遞歸地找到重心并分解樹可以高效解決許多問題動(dòng)態(tài)樹維護(hù)在一些需要?jiǎng)討B(tài)維護(hù)樹結(jié)構(gòu)的問題中重心可以幫助保持樹的平衡網(wǎng)絡(luò)設(shè)計(jì)在計(jì)算機(jī)網(wǎng)絡(luò)中選擇重心作為服務(wù)器位置可以最小化最遠(yuǎn)客戶端的距離游戲AI在一些基于樹形結(jié)構(gòu)的游戲AI中重心可以幫助確定關(guān)鍵位置算法擴(kuò)展可以修改算法找出所有重心一棵樹最多有兩個(gè)重心可以記錄每個(gè)節(jié)點(diǎn)作為重心時(shí)的最大子樹大小可以結(jié)合其他樹算法如直徑計(jì)算、最近公共祖先等7. 性能優(yōu)化與變種實(shí)現(xiàn)雖然標(biāo)準(zhǔn)實(shí)現(xiàn)已經(jīng)很高效但在某些特殊情況下還可以進(jìn)一步優(yōu)化迭代式DFS對(duì)于非常大的樹遞歸可能導(dǎo)致棧溢出可以改為迭代實(shí)現(xiàn)int dfs_iterative(int u) { stackpairint, bool stk; stk.push({u, false}); int size 0; while (!stk.empty()) { auto [node, visited] stk.top(); stk.pop(); if (visited) { int max_size 0, total 1; // 處理子節(jié)點(diǎn)結(jié)果 // ... max_size max(max_size, n - total); if (max_size ans_size) { ans_size max_size; ans_node node; } size total; } else { st[node] true; stk.push({node, true}); for (int i h[node]; i ! -1; i ne[i]) { int j e[i]; if (!st[j]) { stk.push({j, false}); } } } } return size; }并行計(jì)算對(duì)于特別大的樹可以考慮并行計(jì)算子樹的大小動(dòng)態(tài)樹處理如果需要處理動(dòng)態(tài)變化的樹可以研究專門的數(shù)據(jù)結(jié)構(gòu)來維護(hù)樹的重心8. 實(shí)際案例分析讓我們通過一個(gè)具體的例子來演示算法的工作過程?？紤]如下樹結(jié)構(gòu)1 | \ 2 3 | \ 4 5節(jié)點(diǎn)連接情況 1-2, 1-3, 3-4, 3-5算法執(zhí)行過程從節(jié)點(diǎn)1開始DFS訪問節(jié)點(diǎn)1遞歸訪問節(jié)點(diǎn)2和3節(jié)點(diǎn)2是葉子節(jié)點(diǎn)返回size1節(jié)點(diǎn)3遞歸訪問節(jié)點(diǎn)4和5節(jié)點(diǎn)4和5都是葉子節(jié)點(diǎn)各返回size1節(jié)點(diǎn)3得到子樹大小4和5都是1max_size1size1113節(jié)點(diǎn)1得到子樹大小2返回13返回3max_sizemax(1,3)3 還要考慮父節(jié)點(diǎn)方向n-size5-41所以max_sizemax(3,1)3比較并記錄當(dāng)前最小max_size繼續(xù)處理其他節(jié)點(diǎn)...最終會(huì)發(fā)現(xiàn)節(jié)點(diǎn)1和節(jié)點(diǎn)3的max_size都是3而節(jié)點(diǎn)3的max_size是2刪除3后最大連通塊是1-2-3-5或1-2-3-4大小都是3實(shí)際上節(jié)點(diǎn)1和3都是重心。9. 與其他圖算法的比較樹的重心算法與一些其他常見的圖算法有著有趣的聯(lián)系和區(qū)別與樹直徑算法的比較直徑關(guān)注樹中最長(zhǎng)路徑重心關(guān)注平衡性有趣的是樹的直徑的中點(diǎn)往往就是或接近重心與中心點(diǎn)的比較中心點(diǎn)通常指距離所有節(jié)點(diǎn)最遠(yuǎn)的距離最小的點(diǎn)重心與中心點(diǎn)在樹中通常是同一個(gè)點(diǎn)或相鄰的點(diǎn)與割點(diǎn)的比較割點(diǎn)是刪除后增加連通分量數(shù)的點(diǎn)重心不一定是割點(diǎn)除非樹有特定結(jié)構(gòu)但尋找割點(diǎn)的算法與重心算法有相似之處理解這些算法的關(guān)系可以幫助我們更好地選擇和應(yīng)用合適的算法解決問題。10. 編程競(jìng)賽中的應(yīng)用技巧在編程競(jìng)賽中樹的重心相關(guān)問題有一些常見的解題技巧模板準(zhǔn)備事先準(zhǔn)備好加邊函數(shù)和重心算法的模板可以節(jié)省比賽時(shí)間問題轉(zhuǎn)化很多問題看似與重心無關(guān)但可以轉(zhuǎn)化為重心問題如尋找最優(yōu)位置放置設(shè)施最小化最遠(yuǎn)服務(wù)距離樹的平衡分割組合應(yīng)用將重心算法與其他算法結(jié)合使用如重心分解后應(yīng)用線段樹結(jié)合動(dòng)態(tài)規(guī)劃統(tǒng)計(jì)信息與并查集結(jié)合處理連通性邊界處理特別注意n1和n2等小規(guī)模情況的處理調(diào)試方法先在小樹上手動(dòng)驗(yàn)證打印關(guān)鍵變量的中間值比較不同起點(diǎn)的結(jié)果在比賽中遇到樹的問題時(shí)考慮重心往往能提供獨(dú)特的解題視角特別是當(dāng)問題與樹的平衡性或最值性相關(guān)時(shí)。