模板题
846. 树的重心
给定一颗树，树中包含 n 个结点（编号 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;
}加油
