树与图的深度优先遍历（dfs的图论中的应用）
模板题
846. 树的重心
给定一颗树，树中包含 nn 个结点（编号 1∼n）和 n−1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤10^5
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4这道题的比较坑的点是题意很难理解,拿测试用例举例：
拿两个节点1和4举例，先看节点1
如果把节点1拿掉，那么剩余的联通块2、4、7点数分别是：3、4、1，那么删除节点1后连通块点数的最大值就是4
把节点4拿掉，剩余的连通块就是 ：1、3、6，当中的点数分别是：5、2、1，那么删除节点4后剩余连通块节点数的最大值就是5
就这样一直找下去，那么值最小的就是重心，因为出题人偷懒重心有可能有多个不好判断对错，他就改成输出了删除重心后连通块点数的最大值
代码：
#include <iostream>
#include <vector>using namespace std;const int N = 1e5 + 10;
bool st[N];
vector<int> e[N];int n;
int res = 0x3f3f3f3f;int dfs(int u){st[u] = true;int size = 0,sum = 1;for(auto x : e[u]){if(st[x]) continue;int t = dfs(x);size = max(size,t);sum += t;}size = max(size,n - sum);res = min(res,size);return sum;
}int main()
{cin >> n;for(int i = 0,a,b;i < n - 1;i ++){cin >> a >> b;e[a].push_back(b),e[b].push_back(a);}dfs(1);cout << res << endl;return 0;
}树的直径
题目描述
给定一棵 n 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。
输入格式
第一行输入一个正整数 n，表示结点个数。
第二行开始，往下一共 n−1 行，每一行两个正整数 (u,v)，表示一条边。
输出格式
输出一行，表示树的直径是多少。
输入输出样例
输入 #1复制
5 1 2 2 4 4 5 2 3
输出 #1复制
3
说明/提示
数据保证，1≤n≤10^5。
这道题的思路是，随便从一个点出发（我是从1找的）然后找到最底下的点记为target，这个点一定是树的某一边的最下面，那么从target开始，它能到达的最远位置就是直径了
代码：
#include <iostream>
#include <vector>
#include <cstring>using namespace std;const int N = 1e5 + 10;
bool st[N];
vector<int> e[N];int n;
int max_dep = 0,target = 1;void dfs1(int u,int dep)
{st[u] = true;if(dep > max_dep){max_dep = dep;target = u;}for(auto x : e[u]){if(st[x]) continue;dfs1(x, dep + 1);}
}int dfs2(int u){st[u] = true;int sum = 0;for(auto x : e[u]){if(st[x]) continue;sum = max(sum,dfs2(x) + 1);}return sum;
}int main()
{cin >> n;for(int i = 0,a,b;i < n - 1;i ++){cin >> a >> b;e[a].push_back(b),e[b].push_back(a);}dfs1(1,0);// cout << target << endl;memset(st,false,sizeof(st));cout << dfs2(target) << endl;return 0;
}核心城市
题目描述
X 国有 n 座城市，n−1 条长度为 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。
X 国国王决定将 k 座城市钦定为 X 国的核心城市，这 k 座城市需满足以下两个条件：
- 这 k 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
- 定义某个非核心城市与这 k 座核心城市的距离为，这座城市与 k 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。
输入格式
第一行 2 个正整数 n,k。
接下来 n−1 行，每行 2 个正整数 u,v 表示第 u 座城市与第 v 座城市之间有一条长度为 1 的道路。
数据范围：
- 1≤k<n≤10^5
- 1≤u,v≤n,u≠v，保证城市与道路形成一棵树。
输出格式
一行一个整数，表示答案。
输入输出样例
输入 #1复制
6 3 1 2 2 3 2 4 1 5 5 6
输出 #1复制
1
说明/提示
【样例说明】
钦定 1,2,5这 3 座城市为核心城市，这样 3,4,6 另外 3 座非核心城市与核心城市的距离均为 1，因此答案为 1。
这道题是树的直径的应用，首先题目要找到k个核心城市，那么我们先拆分问题，如果只要一个核心城市应该找那个？是不是应该找中心点（也就是树的直径的中点），这样是不是距离就一定是最小值，那么如果再找剩余的k - 1个呢？由于题目是找最小值，那么我们只要求出前k个最大的距离，然后遍历后n - k个距离就是答案了
我们以一棵树举例
算出直径是5后，找中心点
确定1是中心点，那么我们可以先算出每个点的深度（蓝色）
其次在算出每个点能达到的最大深度（紫色）
发现规律了吗？中心点的与非核心城市的距离一定是最大的，其次我们找出前k个与非核心城市距离大的点选做核心城市，然后从非核心城市当中算一下距离即可
代码：
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 1e5 + 10;
int deep[N],dist[N],f[N];
bool st[N];
vector<int> path,e[N];int n, k;
int l = 1, r = 1, max_dep = 0;
int D = 0,center;void dfs1(int u, int dep) {st[u] = true;if (max_dep < dep) {max_dep = dep;l = u;}for (auto x : e[u]) {if (st[x]) continue;dfs1(x, dep + 1);}
}void dfs2(int u, int d) {st[u] = true;if (D < d) D = d, r = u;for (auto x : e[u]) {if (st[x]) continue;dfs2(x, d + 1);}
}void find(int u, int target){st[u] = true;path.push_back(u);if(u == target) return;for(auto x : e[u]){if(st[x]) continue;find(x,target);if(path.back() == target) return;}path.pop_back();
}void bfs(int u)
{memset(deep,-1,sizeof(deep));deep[u] = 0;queue<int> q;q.push(u);while(!q.empty()){auto v = q.front();q.pop();for(auto x : e[v]){if(deep[x] == -1){deep[x] = deep[v] + 1;q.push(x);}}}
}int dfs(int u){st[u] = true;int sum = deep[u];for(auto x : e[u]){if(st[x]) continue;int t = dfs(x);sum = max(sum,t);}dist[u] = sum;return sum;
}bool cmp(int a,int b){return a > b;
}int main() {cin >> n >> k;for (int i = 0, a, b; i < n - 1; i++) {cin >> a >> b;e[a].push_back(b),e[b].push_back(a);}dfs1(1, 0);memset(st,false,sizeof(st));dfs2(l, 0);// cout << "边界点:" << l << " " << r << endl;// cout << "直径:" << D << endl;memset(st,false,sizeof(st));find(l,r);int size = path.size();center = path[size / 2];// cout << "中间点: " << center << endl;bfs(center);memset(st,false,sizeof(st));dfs(center);for(int i = 1;i <= n;i ++) f[i] = dist[i] - deep[i];sort(f + 1,f + n + 1,cmp);// for(int i = 1;i <= n;i ++) cout << f[i] << " ";// cout << endl;int res = -1;for(int i = k + 1;i <= n;i ++) res = max(res,f[i] + 1);cout << res << endl;return 0;
}加油