[ 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存無向樹):

	#define MAXN 100005
	#define INF 0x3f3f3f3f
	int n;
	vector<int> g[MAXN];
	int size[MAXN];
	int ans,balance_size;
	inline void init(){
	for(int i=0;i<n;++i)g[i].clear();
	balance_size=INF;
	}
	void dfs(int u,int pa){
	size[u]=1;
	int max_son_size=0;
	for(size_t i=0;i<g[u].size();++i){
	int v=g[u][i];
	if(v!=pa){
	dfs(v,u);
	size[u]+=size[v];
	max_son_size=max(max_son_size,size[v]);
	}
	}
	max_son_size=max(max_son_size,n-size[u]);
	if(max_son_size<balance_size||/*找編號最小*/(max_son_size==balance_size&&u<ans)){
	ans=u;
	balance_size=max_son_size;
	}
	}
	inline int tree_centroid(){
	dfs(0,-1);
	return ans;
	}

view raw tree_centroid.cpp hosted with ❤ by GitHub