重心

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e6 + 5;
vector<int> g[N];
int d[N], a[N], ans = 1e9, num;
inline void dfs(int u, int fa)
{
	d[u] = 1;
	int max_part = 0; 
	for(int i = 0; i < g[u].size(); i++){//求出节点数量 
		int v = g[u][i];//枚举儿子节点 
		if(v == fa) continue; 
		dfs(v, u); 
		d[u] += d[v];//加上儿子节点数量 
		max_part = max(max_part, d[v]);
	}
	max_part = max(max_part, n - d[u]);//比较除了u以外的连通块 
	if(max_part < ans){//如果更优 
		ans = max_part;//记录 
		num = 0;//更新 
		a[++num] = u;//记录 
	} 
	else if(max_part == ans) a[++num] = u;//记录 
}
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);
		//建树 
	}
	dfs(1, 0);
	sort(a + 1, a + num + 1);//排序 
	cout << num << "\n";//重心个数 
	for(int i = 1; i <= num; i++) cout << a[i] << " ";
	return 0;
}

直径

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e6 + 5;
struct poi{
	int v, w;
};
int d[N];
vector<poi> g[N];
inline void dfs(int u, int fa, int len)
{
	d[u] = len;
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i].v, w = g[u][i].w;
		if(v == fa) continue;
		dfs(v, u, len + w);
	}
}
int main() 
{
    cin >> n >> m;
	for(int i = 1; i <= m; i++){//建树 
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back((poi){v, w});
		g[v].push_back((poi){u, w});
	}    
	dfs(1, -1, 0);//求最远距离 
	int s = 1;
	for(int i = 2; i <= n; i++){
		if(d[i] > d[s]) s = i;//求直径的一个端点 
	}
	dfs(s, -1, 0);//求最远距离
	int t = s;
	for(int i = 1; i <= n; i++){
		if(d[i] > d[t]) t = i;//求直径的另一个端点 
	}
	cout << d[t];//输出直径 
    return 0;
}