[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\)，定義:
\(w_v(u)\)為點\(u\)的權重，\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重，\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和，\(u,v \in V\)

重心的定義是:
以這個點為根，那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)
設
\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)

在
 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下，就是一般的樹重心

性質:

1. 把兩個樹通過一條邊相連得到一個新的樹，那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
2. 把一個樹添加或刪除一個葉子，那麼它的重心最多只移動一條邊的距離。

用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點，即為樹重心
樹重心求法(用vector存無向樹):