求树的重心(链式前向星，vector存边)

树的重心:找到一个点,其所有的子树中最大的子树节点数最少.

给出节点为n的树

下面n-1行为点连接关系

如：

4

1 3

1 2

2 4

一，链式前向星：

#include <iostream>
const int N=2e5+5;
using namespace std;
int head[N],son[N],dp[N],n,k=0,mins=1e9;
//son:某节点的子树节点数
//dp:某节点的最大子节点数
//mins:最小的最大子节点数
bool fa[N];
struct edge
{
	int u,v,nxt;
}e[N];

void  add(int u,int v)
{
	k++;
	e[k].v=v;
	e[k].nxt=head[u];
	head[u]=k;
}

void dfs(int u,int f)

{
	son[u]=1;//叶子节点初始为1
	for(int i=head[u];i;i=e[i].nxt)//i=e[i].nxt取得前向
	{
		int v=e[i].v;
		if(v!=f)//取得节点不是父节点
		{
			dfs(v,u);
			son[u]+=son[v];
			dp[u]=max(dp[u],son[v]);//与u的各个子树节点比较
		}
	}
	dp[u]=max(dp[u],n-son[u]);//u最大的子树节点数与其父节点的子树节点数比较
    mins=min(mins,dp[u]);
}

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,0);
	for(int i=1;i<=n;i++)
	{
		if(dp[i]==mins)
		{
		    cout<<"节点编号： "<<i<<endl;
		}
	}
}

输出：

节点编号： 1
节点编号： 2

二，vector

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool visit[205];//判断是否访问过
struct edge
{
	vector<int> v;
}e[205];

int ans[205],n,minm=1e9,dp[205];
//ans存子树节点数
//minm存最小的最大节点数
//dp存某个节点的子树的最大节点数
void dfs(int u)
{
	visit[u]=true;
	ans[u]=1;
	for(vector<int>::iterator it=e[u].v.begin();it!=e[u].v.end();it++)//逐一遍历u的子节点
	{
		int to=*it;
		if(!visit[to])
		{
		
			visit[to]=true;
			dfs(to);
			ans[u]+=ans[to];//逐一加上子节点的的节点数
			dp[u]=max(dp[u],ans[to]);
			visit[to]=false;//回溯
		}

	}
	dp[u]=max(dp[u],n-ans[u]);
	minm=min(dp[u],minm);
}

int main()
{

		memset(visit,false,sizeof visit);
		memset(ans,0,sizeof ans);
		cin>>n;
		for(int i=1;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			e[x].v.push_back(y);
			e[y].v.push_back(x);
		}
		dfs(1);
		for(int i=1;i<=n;i++)
		{
			if(dp[i]==minm)
			cout<<"节点编号： "<<i<<endl;
		}
	
}