树的重心模板 / poj1655

前言

树的重心有一些很好的性质，在树形dp中也常常出现，留个模板来备用

树重心的性质：

1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
3. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
5. 对于树上的每一个点，计算其所有子树中最大的子树节点数，重心是这个值最小的点。

求法也很简单，dfs遍历每个节点，求出每个节点的子树节点个数的最大值，保存比较即可

一、 例题 poj1655

题目链接：poj-1655

二、 思路及代码 1. 思路

一道模板题，直接套模板 num[]数组保存子树节点的个数，轮询max(num[i], n - num[i])即可

2. 代码

代码如下 ：

#include 
#include 
#include 
const int maxn = 4e4 + 4;
using namespace std;
struct e {
  int to, next;
} edge[maxn];
int cnt, n;
int pos, ans;
int head[maxn], num[maxn];
void init() {
  cnt = 0, pos = 1, ans = n;
  for (int i = 0; i