首页 > 代码库 > 树的重心

树的重心

部分转载自:http://blog.csdn.net/u013076044/article/details/45915745

 

定义

找到一个点,其所有子树中最大的子树节点数最少,那么这个点就是整棵树的重心。

在树的总点数为偶数时,可能会有两个重心。

 

性质

性质 1 :树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。

性质 2 :把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。

性质 3 :一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。

 

求法

在找树的重心时,我们先随意确定一个根,之后通过一遍dfs将所有子树的大小求出来。

如果有一个点 i 满足 2 * size[i] >= n ,并且它的儿子都满足 2 * size[son[i]] <= n ,那么这个点就是树的重心。

至于代码有些不同。

技术分享
 1 inline void dfs(int u) 2 { 3     int i, v; 4     size[u] += 1; 5     for(i = head[u]; i != -1; i = next[i]) 6     { 7         v = to[i]; 8         if(v != f[u]) 9         {10             f[v] = u;11             dfs(v);12             size[u] += size[v];13         }14     }15     if(2 * size[u] >= tot && !ans) ans = u;16 }
View Code

 

树的重心