点分治

本质就是树上的分治。

序列的分治是不断地将序列二分，而对于树则需要利用树的重心。

树的重心

定义：树中一节点，以它为根的最大的子树最小。

求解：跑一遍\(dfs\)求解即可。

void get_rt(int u, int fa){
	siz[u] = 1, max_siz[u] = 0;
	for(auto v : T[u]){
		if(v.fir == fa || vis[v.fir]) continue;
		get_rt(v.fir, u);
		siz[u] += siz[v.fir];
		max_siz[u] = max(max_siz[u], siz[v.fir]);
	}
	max_siz[u] = max(max_siz[u], sum - siz[u]);
	if(max_siz[rt] > max_siz[u]) rt = u;
}

注：

1：初始值\(maxsiz[rt] = INF\)，\(maxsiz[rt]\)保存的是最小值。

2：\(maxsiz[u]\)清空。

分治部分

先找到当前树的重心，\(calc\)后把当前重心标记，再递归求解它的所有邻点。

void solve(int now){
	vis[now] = 1;
	clac(now);
	for(auto v : T[now]){
		if(vis[v.fir]) continue;
		sum = siz[v.fir];
		max_siz[rt] = 0x3f3f3f3f;
		get_rt(v.fir, now);
		solve(rt);
	}
}

注：

1：先求解出\(sum, rt\)后再递归\(solve(rt)\)。

2：\(maxsiz[rt] = INF\) 。

3：注意\(vis\)数组。