luogu：https://www.luogu.com.cn/problem/P5536

\(n\) 座城市，\(n - 1\) 條道路，任意兩座城市能通過若干條道路互通，將其中 \(k\) 座城市定義為核心城市。
\(k\) 座城市可以通過道路在不經(jīng)過其它城市的情況下兩兩互通。
定義某個非核心城市與這 \(k\) 座城市的距離為這座城市到核心城市的最小距離，選擇的核心城市要滿足所有非核心城市的距離最大值最小。求出這個最小距離。

兩遍 \(dfs\) 求直徑

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
LL n, k, c, ans, d[N], pa[N], md[N], a[N];
vector <LL> g[N];
void dfs(LL u, LL fa){
	for (auto v : g[u]){
		if (v == fa) continue;
		d[v] = d[u] + 1;
		if (d[v] > d[c]) c = v;
		dfs(v, u);
	}
}
void findC(LL u, LL fa){
	for (auto v : g[u]){
		if (v == fa) continue;
		d[v] = d[u] + 1;
		pa[v] = u;
		if (d[v] > d[c]) c = v;
		findC(v, u);
	}
}
void calD(LL u, LL fa){
	md[u] = d[u];
	for (auto v : g[u]){
		if (v == fa) continue;
		d[v] = d[u] + 1;
		calD(v, u);
		md[u] = max(md[u], md[v]);
	}
}
int main(){
	cin >> n >> k;
	for (int i = 1; i < n; i ++ ){
		LL u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	d[c] = 0;
	findC(c, 0);
	LL t = d[c];
	for (int i = 1; i <= (t + 1) / 2; i ++ )
		c = pa[c];
	d[c] = 0;
	calD(c, 0);
	for (int i = 1; i <= n; i ++ )
		a[i] = md[i] - d[i] + 1;
	sort(a + 1, a + n + 1, [](LL a, LL b){
		return a > b;
	});
	for (int i = k + 1; i <= n; i ++ )
		ans = max(ans, a[i]);
	cout << ans << "\n";
	return 0;
}

\(dp\) 求直徑

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
LL n, k, c, dis, ans, d1[N], d2[N], d[N], pa[N], md[N], a[N];
vector <LL> g[N];
void dfs(LL u, LL fa){
	d1[u] = d2[u] = 0;  //注意距離的初始化
	for (auto v : g[u]){
		if (v == fa) continue;
		dfs(v, u);
		LL t = d1[v] + 1;
		if (t > d1[u])
			d2[u] = d1[u], d1[u] = t;
		else if (t > d2[u])
			d2[u] = t;
	}
	if (d1[u] + d2[u] > dis){
		dis = d1[u] + d2[u];	//找到最長的兩條鏈之和 
		c = u;	//重心 
	}
}
void findC(LL u, LL fa){	//求出直徑的路徑 
	for (auto v : g[u]){
		if (v == fa) continue;
		d[v] = d[u] + 1;
		pa[v] = u;
		if (d[v] > d[c]) c = v;
		findC(v, u);
	}
}
void calD(LL u, LL fa){
	md[u] = d[u];
	for (auto v : g[u]){
		if (v == fa) continue;
		d[v] = d[u] + 1;
		calD(v, u);
		md[u] = max(md[u], md[v]);
	}
}
int main(){
	cin >> n >> k;
	for (int i = 1; i < n; i ++ ){
		LL u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	d[c] = 0;
	findC(c, 0);
	LL t = d[c];
	for (int i = 1; i <= (t + 1) / 2; i ++ )	//找到直徑的中點 
		c = pa[c];
	d[c] = 0;
	calD(c, 0);
	for (int i = 1; i <= n; i ++ )
		a[i] = md[i] - d[i] + 1;
	sort(a + 1, a + n + 1, [](LL a, LL b){
		return a > b;
	});
	for (int i = k + 1; i <= n; i ++ )
		ans = max(ans, a[i]);
	cout << ans << "\n";
	return 0;
}