MHT Root, Tree Centroid

Published in

learning note

Aug 20, 2021

Keywords: minimum height trees (MHTs), tree centroid, topological sort, centroid decomposition

前言

剛好看到一個樹的分治法，過程中需要找到樹的重心。後來又看到另一個看似相像，但是想法截然不同的樹問題，特別將兩者放上來比較。

從樹中找到一個或若干根結點，使的其所有子樹的最大連通分量最小。

從任一點出發作為根結點，可以遞迴得到在該點之下的最大連通分量，由於整棵樹總結點數量固定，因此也可求得該點之上的連通分量，等同於求得以該點為根的所有連通分量。

求樹重心的一個很重要的用途就是對樹做Divide and Conquer優化(Centroid Decomposition of Tree)，找到一個點將樹切割成若干連通分量 <= n/2的子樹，對每個子樹做統計後再透過根結點合併這些樹，如下圖。

從樹中找到一個或若干根結點，使其所有子樹的最大深度最小。

最大深度問題不能採用dfs的原因在於，雖然能判定其上的節點數有點少，但卻無法在dfs過程中確定其上的節點最深為多少。

最大深度問題可以換個方式思考，假設我將每個葉節點(只被一個edge接觸的點)都選出來，如果圖中還有未被選到的點，代表這些葉節點必然不會是根，因此將這些葉節點剃除之後，在新的圖內重新挑選一次葉節點。

其實就是做拓撲排序(topological sort)。