本题解寻找重心和统计路径均使用DFS

#include<iostream>
#include<vector>
using namespace std;
int n,max_[1000005],size_[100005],cen=0,ssum=0;//max_[u]储存节点u的最大子树，size_[u]储存节点u及以下的子树大小
vector<int>g[1000005];

void addedge(int u,int v){
    g[u].push_back(v);
    g[v].push_back(u);
}

void findcen(int u,int fa){             //此函数用于寻找重心
    size_[u]=1,max_[u]=0;               //将当前节点作为根节点并进行初始化
    for (auto v:g[u]){
        if (v==fa)continue;
        findcen(v,u);
        size_[u]+=size_[v];
        max_[u]=max(max_[u],size_[v]);  //更新为最大子树的大小
    }
    max_[u]=max(max_[u],n-size_[u]);    //根节点方向子树大小=总大小-其他方向大小,通商进行更新
    if (max_[u]<max_[cen] || (max_[u]==max_[cen] && u<cen)){    
        cen=u;
    }
}

void getpath(int u,int fa,int sum){     //此函数用于统计总路径长度
    ssum+=sum;                          
    for (auto v:g[u]){
        if (v==fa)continue;
        getpath(v,u,sum+1);
    }
}

int main()
{
    max_[0]=(int)1e9;       //注意这里一定要将初始重心的最大子数大小设置为无穷大
    cin >> n;               //否则第21行的判断中会一直认为0节点最优
    for (int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
    }
    findcen(1,0);

    getpath(cen,0,0);
    cout << cen << " " << ssum;
    return 0;
}

DFS 永远的神, BFS 根本不配

#include<iostream>
#include<vector>
#define N 50005
using namespace std;
int n,c;
vector<int>g[N];
int size[N];
int ma[N];
void getc(int u,int fa)
{
	size[u]=1;//初始化只有自己 
	ma[u]=0;
	for(auto v:g[u])
	{
		if(v==fa)continue;
		getc(v,u);//递归子结点 
		size[u]+=size[v];//size[u]指所有子结点的大小 
		ma[u]=max(ma[u],size[v]);//这个点为重心时,找出最大的子结点大小 
	}
	ma[u]=max(ma[u],n-size[u]);//这个点为重心时,父亲结点大小 
	if(c==0 || ma[u]<ma[c] || (ma[u]==ma[c] && u<c))
		c=u;
	/*
	c==0 的情况是目前没有选出重心,直接沿用 
	ma[u]<ma[c] 这个就不说了 
	ma[u]==ma[c] && u<c 这个是判断哪个重心结点编号更小 
	*/
}
int dfs(int u,int fa,int deep)
{
	int sum=deep;
	for(auto v:g[u])
	{
		if(v==fa)continue;
		sum+=dfs(v,u,deep+1);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	getc(1,0);
	cout<<c<<" "<<dfs(c,0,0);
	return 0;
}

题意

找树的“中心”，使每个结点到他的距离加起来（距离和）最小。

思路

这个“中心”其实是重心。重心的性质^[1]有一个就是“树中所有点到某个点的距离和中，到重心的距离和最小”。

所以我们要求的就是重心，如何求重心呢？

利用重心的另一个性质：以重心为树根时，所有子树的大小不超过全树大小的一半。根据这个性质我们可以用 DFS 求出来重心。注意最大子树大小最小（理解不了看代码）的结点才是重心，因为小于全树大小一半在非重心也有可能做到。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
vector<int> a[N];
int n,root;	// 结点个数；重心
int sz[N],stsz[N] = {0x7fffffff};	// 树的大小；以 i 为根结点时最大子树的大小
int dis[N],sum;	// 每个点到重心的距离；距离和
// 找重心
void dfs(int u,int f){
	sz[u] = 1;
	for (int v : a[u]){
		if (v != f){
			dfs(v,u);
			sz[u] += sz[v];
			stsz[u] = max(stsz[u],sz[v]);
		}
	}
	stsz[u] = max(stsz[u],n - sz[u]);	// 父节点的子树
	if (stsz[u] < stsz[root] || stsz[u] == stsz[root] && u < root)	root = u;
}
// 计算每个点到重心的距离
void bfs(int root){
	queue<pair<int,int>> q;
	q.push({root,0});
	while (!q.empty()){
		int u = q.front().first,f = q.front().second;
		q.pop();
		for (int v : a[u]){
			if (v != f){
				dis[v] = dis[u] + 1;
				sum += dis[v];
				q.push({v,u});
			}
		}
	}
}
int main(int argc, char **argv){
	cin >> n;
	for (int i = 1;i < n;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs(1,0);	// 找重心
	bfs(root);	// 计算每个点到重心的距离
	cout << root << ' ' << sum;
	return 0;
}

呜呜呜，终于吃上题解了

由于树上的书上的题解一个DFS一个BFS，太不规整了，直接全用DFS！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>edge[100001];
ll center,n,sum;
ll len[100001];
ll pss[100001]={1111111111};
void lfc(ll num,ll p){
	len[num]=1;
	for(auto i:edge[num]){
		if(i==p)continue;
		lfc(i,num);
		len[num]+=len[i];
		pss[num]=max(pss[num],len[i]);
	}
	pss[num]=max(pss[num],n-len[num]);
	if(pss[center]>pss[num]||(pss[center]==pss[num]&&num<center))center=num;
}
void crs(ll num,ll p,ll add){
	sum+=add;
	for(auto i:edge[num]){
		if(i==p)continue;
		crs(i,num,add+1);
	}
}
int main(){
	cin>>n;
	for(ll i=1;i<n;i++){
		ll u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	lfc(1,1);
	crs(center,center,0);
	cout<<center<<" "<<sum;
}