树的直径个人学习笔记（含例题）

1.树的直径 树的直径定义为一颗树的最远的两个点对d(i,j)对应链的长度. 如何求树的直径? 采用两次dfs的方法。第一次dfs先求出对于1号点来说最远的点u.那么u一定是该直径上的一端. 然后我们进行第二次dfs.以u节点为根,找到最深的子节点v.那么路径(u->v)就是这个树的直径. 代码: 注意注意注意di是全局变量,不能传参,否则会错,要传参的话得是引用类型,每次使用前需要清空. 在第三个函数中(U,V)是引用类型,就是代表找到的两个最远的点啦. 并且得到一个最终的 f a [ u ] fa[u] fa[u]数组,方便还原这个直径.

int depth[maxn];int di = 0;
void dfs1(int u,int f,int &U){
	if(depth[u]>di){
		di = depth[u];
		U = u;
	}
	for(auto [v,w] : G[u]){
		if(v==f) continue;
		depth[v] = depth[u] + w;
		dfs1(v,u,U);
	}
}
int fa[maxn];
void dfs2(int u,int f,int &V){
	fa[u] = f;
	if(depth[u]>di){
		di = depth[u];
		V = u;
	}
	for(auto [v,w] : G[u]){
		if(v==f) continue;
		depth[v] = depth[u] + w;
		dfs2(v,u,V);
	}
}
void find_di(int &U,int &V){
	di = 0;
	memset(depth,0,sizeof(depth));
	dfs1(1,0,U);
	di = 0;
	memset(depth,0,sizeof(depth));
	dfs2(U,0,V);
}

例题1: P5536 【XR-3】核心城市

来自 https://www.luogu.com.cn/problem/P5536 题目描述 X 国有 n 座城市，n−1 条长度为 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。 X 国国王决定将 k 座城市钦定为 X 国的核心城市，这 k 座城市需满足以下两个条件： 1. 这 kk 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。 2. 定义某个非核心城市与这 k 座核心城市的距离为，这座城市与 k 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

思路：贪心地想,该最小值如何得到,在k=1的时候.必然要设定该城市位于树直径的中点上,只有这样才能最小化所有点到该点距离的最大值. 那么继续思考,如何才会使得答案变得更小.必然是选取与该中点连接的某个点u.选取之后答案不会变得更差. 设其他点u到中点mid的距离为dep[u];那么,我们只需要贪心地选取深度为前k-1个. 实现:先求出树的直径两个点(U,V).找到该链上的中点mid.以该mid为根,重建该树,统计每个点最深孩子与自己高度之差. 排序,贪心认为选取前k大的点（一定包含树根,且选择的点一定是连通的,稍加思考即可知道）,那么ans[k+1]+1就是答案

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
vector G[maxn];
int depth[maxn];int max_depth[maxn];
int di=0;
void dfs1(int u,int f,int &U){
	if(depth[u]>di){
		U = u;di = depth[u];
	}
	for(auto v : G[u]){
		if(v==f) continue;
		depth[v] = depth[u] + 1;
		dfs1(v,u,U); 
	}
}
int fa[maxn];
void dfs2(int u,int f,int &V){
	fa[u] = f;
	if(depth[u]>di){
		di = depth[u];V = u;
	}
	for(auto v : G[u]){
		if(v==f) continue;
		depth[v] = depth[u] + 1;
		dfs2(v,u,V);
	}
}
void dfs3(int u,int f){
	max_depth[u] = depth[u];
	for(auto v :G[u]){
		if(v==f) continue;
		depth[v] = depth[u] + 1;
		dfs3(v,u);
		max_depth[u] = max(max_depth[u],max_depth[v]);
	}
}
int main(){
//    freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k;cin>>n>>k;
	for(int i=1;i>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int U,V;
	di = 0;
	dfs1(1,0,U);
	memset(depth,0,sizeof(depth));
	di = 0;
	dfs2(U,0,V);
	int mid = V;
	for(int i=1;iu>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	int U,V;
	find_di(U,V);
	int ans = 0;
	dfs3(V,0);
	for(int i=1;i