[基础算法6] 树的重心
题目描述
题目描述：
给定一颗树，树中包含N个结点（编号从1-N），和N- 1 条无向边。请你找到树的重心，并输出 将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个结点被 称为树的重心。
输入格式：
第一行包含整数N，表示 树的结点数，１＜＝Ｎ＜＝１ｅ５ ，接下来Ｎ－１行，每行包含两个整数ａ和ｂ，表示 ａ和ｂ之 间存在一条边。
输出格式：
输出一个整数 N，表示 将重心删除后，剩余各个连通块中点数的最大值。
样例输入 复制
9
1 4
1 2
2 6
2 5
6 3
6 7
7 9
7 8
样例输出 复制
4
来源/分类
树DP
程序：
#include <iostream>using namespace std;const int N=1e5+10;bool vis[N];int E[2*N],ne[2*N],h[N],id,ans=0x3f3f3f3f,n;int dfs(int u){ vis[u]=true;//标记u这个点被搜过 int size=0;//记录u的最大子树的结点数 int sum=1;//记录以u为根的子树的结点数 for(int i=h[u];i!=0;i=ne[i])//i是边的编号 { int j=E[i];//j是u的邻接点 if(vis[j]) continue;//避免向上查找 int s=dfs(j);//s是以j为根的子树的结点数 size=max(size,s);//记录u的最大子树的结点数 sum+=s;//累加u的各个子树的结点数 } ans=min(ans,max(size,n-sum));//更新答案 return sum;//返回以u为根的子树的结点数}void add(int x,int y)//邻接表{ E[++id]=y; ne[id]=h[x]; h[x]=id;}//加边int main(){ cin>>n; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; add(x,y); add(y,x);//建图 } dfs(1); cout<<ans<<endl; return 0;}