洛谷 P5536 【XR-3】核心城市（贪心 + 树形 dp 寻找树的中心）

【XR-3】核心城市

题目描述

X 国有 $n$ 座城市，$n-1$ 条长度为 $1$ 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国国王决定将 $k$ 座城市钦定为 X 国的核心城市，这 $k$ 座城市需满足以下两个条件：

1. 这 $k$ 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
2. 定义某个非核心城市与这 $k$ 座核心城市的距离为，这座城市与 $k$ 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

输入格式

第一行 $2$ 个正整数 $n,k$。

接下来 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示第 $u$ 座城市与第 $v$ 座城市之间有一条长度为 $1$ 的道路。

数据范围：

• $1\le k<n\le 10^5$。
• $1\le u,v\le n,u\ne v$，保证城市与道路形成一棵树。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #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 个点作为核心城市，其他点到核心城市的距离 为 他们到这些城市的最短距离 s。

这些 最短距离中有一个最大距离，把这个 最大距离作为这个核心城市群的参考值 dist，要你求所有不同核心城市中 dist 最小的。

一句话点破，之前我们是找树的中心，目的是找到一个点，那么本题就是它的高配升级版，现在我们要找的是一个中心点群。

思路：

遇到这种复杂度题我们要先简单化，比如题中问我们 k 座城市，那我们就先假设 k 为 1 是什么情况。

• 显然，当 k 为 1 时，核心城市就是 树的中点，设为 u。（联系之前做过的一道题：树的中心）

当 k == 1 时找树的中心，代码放这里，联系之前所学自己体会：

int dfs_d(int u, int father)
{
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		int d = dfs_d(j, u) + 1;
		if (down1[u] < d) down2[u] = down1[u], down1[u] = d, p[u] = j;
		else if (down2[u] < d) down2[u] = d;
	}

	return down1[u];
}

void dfs_u(int u, int father)
{
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		if (p[u] == j) up[j] = max(up[u], down2[u]) + 1;
		else up[j] = max(up[u], down1[u]) + 1;
		dfs_u(j, u);
	}
}

int solve1()
{
	dfs_d(1, -1);
	dfs_u(1, -1);
	int u = 0, res = inf;
	for (int i = 1; i <= n; ++i)
	{
		int tmp = max(down1[i], up[i]);
		if (res > tmp) res = tmp, u = i;
	}
	return u;	// u 号点即为中心
}

那么，对于 k > 1 的情况呢？

我们在纸上画一张图：（令 k = 5）

对于这棵树，红点显然是树的中心，核心城市应该是绿框中的点。

这启发我们从 贡献的角度 思考：

• 要使得 任意非核心城市 与 这 k 座核心城市 的 距离最大值 最小，那我们 每次放置核心城市，都使 当前最大值 -1，减 k 次 即可。

贪心实现：

• 重构 这颗树，以 树的中心 u 当作根结点，除了 根结点 u 以外，所处深度最大的点 显然 占据着最大值，贡献最大，我们就往它这个 分支/子树 的方向扩散似的放一个 核心城市（从根节点扩出去），扩出去后，该子树所有的点对答案的贡献都 -1

上述过程可以直接 优先队列 bfs 模拟，直接 排序处理 也可以。

对于所有点按照 “dis[i] = 往下走能到的最大深度 − 所处的深度” 从大到小排序，前 k 个点 就是我们的 核心城市 了。

当然了，排序前我们还要 用 dfs 从树的中心 u 开始，预处理出 每个点的深度 depth[i] 和 能到达的最大深度 maxd[i]

代码如下，注意 向下递归 和 向上回溯 的操作：

void dfs1(int u, int fa)
{
	maxd[u] = depth[u];	//先对 maxd 赋初值
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == fa) continue;
		depth[j] = depth[u] + 1;	//显然
		dfs1(j, u);
		maxd[u] = max(maxd[u], maxd[j]);	//回溯的时候更新 maxd，经过模拟不难得出
	}
}

答案为 dis[k] + 1（dis 数组 我是从 下标为 0 开始存）

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
struct reader {
    
	template <typename Type>
	reader& operator>> (Type& ret) {
    
		register int f = 1; ret = 0; register char ch = getchar();
		for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
		for (; isdigit(ch); ch = getchar()) ret = (ret << 1) + (ret << 3) + ch - '0';
		ret *= f; return *this;
	}
} fin;

const int N = 1e5 + 10, M = N << 1, inf = 0x3f3f3f3f;
int n, k;
int h[N], e[M], ne[M], idx;
int down1[N], down2[N], up[N], p[N];
int depth[N], maxd[N];

void add(int a, int b)
{
    
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs_d(int u, int father)
{
    
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == father) continue;
		int d = dfs_d(j, u) + 1;
		if (down1[u] < d) down2[u] = down1[u], down1[u] = d, p[u] = j;
		else if (down2[u] < d) down2[u] = d;
	}

	return down1[u];
}

void dfs_u(int u, int father)
{
    
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == father) continue;
		if (p[u] == j) up[j] = max(up[u], down2[u]) + 1;
		else up[j] = max(up[u], down1[u]) + 1;
		dfs_u(j, u);
	}
}

int solve1()
{
    
	dfs_d(1, -1);
	dfs_u(1, -1);
	int u = 0, res = inf;
	for (int i = 1; i <= n; ++i)
	{
    
		int tmp = max(down1[i], up[i]);
		if (res > tmp) res = tmp, u = i;
	}
	return u;
}

void dfs1(int u, int fa)
{
    
	maxd[u] = depth[u];
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == fa) continue;
		depth[j] = depth[u] + 1;
		dfs1(j, u);
		maxd[u] = max(maxd[u], maxd[j]);
	}
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		fin >> n >> k;
		memset(h, -1, sizeof h);
		int t = n - 1;
		for (int i = 0; i < t; ++i)
		{
    
			int u, v; fin >> u >> v;
			add(u, v), add(v, u);
		}
		int u = solve1();//找中点
		dfs1(u, -1);
		vector<int> dis;
		for (int i = 1; i <= n; ++i)
		{
    
			dis.push_back(maxd[i] - depth[i]);
		}
		sort(dis.begin(), dis.end(), greater<int>());
		printf("%d\n", dis[k] + 1);
	}

	return 0;
}