[图论]——[树形结构]——树的重心

大家好，欢迎来到IT知识分享网。

树的重心定义

可以类比一下物理上的重心，一个物体本来质量是不均匀的，但是在重心这个质点上就可以把这个物体视为均匀的 （口胡） 那么树的重心可以这样理解：以这个点为根节点，它的多棵子树 “尽可能平衡”。

树的重心的性质

一下性质摘抄自百度百科。

1. 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
2. 把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
3. 一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
4. 一棵树最多有两个重心，且相邻。

树的重心的求法

第一种方法是根据定义求树的重心。

void dfs(int u, int fa) { size[u] = 1; dp[u] = 0; for(int i=head[u];i;i=edge[i].next) { int v = edge[i].to; if(v==fa) continue; dfs(v, u); size[u] += size[v]; dp[u] = max(dp[u], size[v]); } dp[u] = max(dp[u], N-size[u]); //上面提到的处理 if(dp[u]<dp[ans]) ans = u; } 

也可以用重心性质求树的重心
利用性质：树中所有点到某个点的距离和中，到重心的距离和最小。
还是先指定一个根节点，把无根树变成有根树。size[ i ]同上。
deep[ i ]为结点 i 的深度。dis[ i ]为所有点到点 i 的距离和。

定义 subtree(x) 表示以 x 为根的子树中点的集合。显然 subtree(x)∈n

1. 考虑不在 subtree(x) 中的点，它们到 u 的距离和是 它们到 v 的距离和加上 (N-size[u])
2. 而对于那些在 subtree(u) 中的点，它们到 u 的距离和就是 它们到 v 的距离和再减去 (size[u])

所以合并两式，$dis[u]=dis[v]+N-2\ast size[u]$

代码：

void dfs1(int u) { size[u] = 1; for(int i=head[u];i;i=edge[i].next) { int v = edge[i].to; if(deep[v]) continue; deep[v] = deep[u]+1; dfs1(v); size[u] += size[v]; } } void dfs(int u, int fa) { dis[u] = dis[fa]+N-2*size[u]; for(int i=head[u];i;i=edge[i].next) { int v = edge[i].to; if(v==fa) continue; dfs(v, u); } } 

例题

模板: 洛谷P1395 会议.

找两个重心：POJ 1655 Balancing Act.

思维: CF1406C Link Cut Centroids.