树的重心

树的重心

首先，我们要知道，什么是重心 树的重心定义为，当把节点x去掉后，其最大子树的节点个数最少(或者说成最大连通块的节点数最少)，那么节点x就是树的重心。 他有以下几个性质 1、删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心，且相邻； 2、树中所有节点到重心的距离之和最小，如果有两个重心，那么它们距离之和相等； 3、两个树通过一条边合并，新的重心在原树两个重心的路径上； 4、树删除或添加一个叶子节点，重心最多只移动一条边。 还有，一棵树，重心最多2个，n%2= =0有2个，n%2= =1有一个 运用第一个性质，可以解决大多数问题

题目描述

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。 输入格式 输入：第一行一个整数n，表示树的结点个数。（n<100） 接下来n-1行，每行两个数i，j。表示i和j有边相连。 输出格式 输出：第一行一个整数k，表示重心的个数。 接下来K行，每行一个整数，表示重心。按从小到大的顺序给出。 样例 样例输入 7 1 2 1 3 2 4 2 5 3 6 3 7 样例输出 1 1

分析

运用第一个性质，我们可以排除那些不是重心的，然后，输出剩下的 可以统计任选一个节点为根，把无根树变成有根树，然后dp[i]表示以i为根的子树的节点个数 dp[i]=∑dp[son]+1 这只是部分子树，还有当前节点的长辈，节点总数为n-dp[now]，然后在做比较

#include<bits/stdc++.h> using namespace std; int n; int x,y; int dp[100054]; vector<int>g[10005]; vector<int>ans; int vis[10005]; void dfs(int x) { bool flag=1; dp[x]=1; for(int i=0;i<g[x].size();i++) { int v=g[x][i]; if(vis[v]) { continue; } vis[v]=1; dfs(v); dp[x]+=dp[v]; if(dp[v]>n/2) { flag=0; } } if(n-dp[x]>n/2) { flag=0; } if(flag) { ans.push_back(x); } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d %d",&x,&y); g[x].push_back(y); g[y].push_back(x); } vis[1]=1; dfs(1); printf("%d\n",ans.size()); if(ans.size()==1) { printf("%d",ans[0]); } else { printf("%d\n%d",min(ans[0],ans[1]),max(ans[0],ans[1])); } }