一、题目背景和问题描述
本题大意是n (3 \\leq n \\leq 1000) 台机器连起来成一个树状网络，其中叶子结点是客户端，其他节点是服务器。目前有一台服务器正在提供VOD（Video On Demand）服务，虽然视频质量本身不错，但是对于那些离他很远的客户端而言网络延迟却是难以接受的。现在需要在特定的节点上面安装该服务副本，使得所有的客户端距离他最近的VOD服务器距离不会超过给定的整数k，并且所安装的服务器还要尽可能的少。题目链接：
输入格式：
第一行是数据组数T。对于每一组数据：第一行为树中的节点个数n（包含服务器和客户端）下面一行包含两个整数s和k（）。接下来的n-1行每一行包含两个整数代表两个节点之间的一条边。
输出格式：
对于每一组数据，输出一个整数即还需要安装VOD服务副本的最小值。
输入样例
2
14
12 2
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
14
3 4
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
输出样例：
1
0
二、整体思路
根据题目意思，本题需要将无根数变成有根树，因为天然提供了一个根节点s，也就是VOD服务器所在的位置，方便我们建树。对于那些已经满足条件的客户端，我们可以当做他们不存在，如下图所示，我们可以忽略其中的13，11, 1三个叶子结点。
因为题目是需要求最小值，所以我们核心思路思路就是采用有根树+贪心策略来求解。我们将原始服务器s作为树的根，将无根数转化成为有根树，客户端距离服务器的位置需要在给定整数k以内，那么这道题目还需要利用到树的深度，天然使用BFS更加形象方便理解。
建树的过程之中采用邻接表的方法来记录给定的树状图，通过一次BFS求出给定的任意节点u的parent[u]和depth[u]，也就是节点u的父节点和节点u的深度（即到根节点的距离）。要求出最小需要VOD副本数目，也就是要优先考虑最不可能被覆盖的客户端，即从深度最大的叶子结点u开始处理，需要从u向根节点的方向走k步到达节点p，在p处放置VOD副本，然后再将距离 p 不超过 k 的所有节点标记为已覆盖。如果所有的客户端均被覆盖，我们就可以得到题目所需要的答案。
假设当前需要处理的最大深度是尚未被覆盖的客户端u，从u开始向上走k步到达节点p。那么所有的可行方案都必须至少新增一个副本才有可能覆盖u，p处放置副本一定能够覆盖u。任意能够覆盖u的服务器副本都不能超过距离k，而相较于放在离u更近的节点上，放在p处能够更加靠近树的上层，并且更加容易覆盖其他没有被覆盖的客户端，所以这一个选择就可以被某一个最优方案包含，这也就体现了贪心策略的应用。
算法步骤如下：
-
首先需要选择合适的数据结构读取树，我们可以考虑vector<vector<int>>的二维数组读取网状图，结合vector<int>存放每一个节点的父节点和他的深度，就可以记录下树里面每一个节点的信息
-
以s为根进行BFS，计算父节点和深度
-
找到所有读书为1的客户端，也就是叶子结点，用动态数组存图，也就是在邻接表之中，行数组的大小如果是1的话，就代表这个节点只有一条边，也就是叶子结点
-
从s开始执行有限深度的BFS，这里的有限深度就是k，将所有当前服务器能够覆盖的范围全部标记上
-
将客户端按照depth从大到小排序
-
依次处理每一个客户端：如果已经覆盖那么就跳过，全部覆盖的时候就满足条件了。否则就沿着当前客户端向上走k步（这里的向上走在实际操作的时候可以利用父节点的记录连续找k次父节点）到达p,在p处放置服务器副本，计数器加1。然后从p开始继续进行有限深度的BFS，更新放置新服务器副本之后的覆盖范围。
-
最终按照要求格式输出。本题没有特殊的格式，注意换行即可。
三、代码实现
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T–) {
int n;
cin >> n;
int s, k;
cin >> s >> k;
vector<vector<int>> graph(n + 1);
for (int i = 0; i < n – 1; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> parent(n + 1, 0);
vector<int> depth(n + 1, 0);
queue<int> q;
q.push(s);
parent[s] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (v == parent[u]) {
continue;
}
parent[v] = u;
depth[v] = depth[u] + 1;
q.push(v);
}
}
vector<int> clients;
for (int u = 1; u <= n; ++u) {
if (graph[u].size() == 1) {
clients.push_back(u);
}
}
sort(clients.begin(), clients.end(),
[&](int a, int b) {
return depth[a] > depth[b];
});
vector<bool> covered(n + 1, false);
auto markCovered = [&](int start) {
queue<pair<int, int>> bfs;
vector<bool> visited(n + 1, false);
bfs.push({start, 0});
visited[start] = true;
while (!bfs.empty()) {
auto [u, distance] = bfs.front();
bfs.pop();
covered[u] = true;
if (distance == k) {
continue;
}
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
bfs.push({v, distance + 1});
}
}
}
};
markCovered(s);
int answer = 0;
for (int client : clients) {
if (covered[client]) {
continue;
}
int server = client;
for (int step = 0; step < k; ++step) {
server = parent[server];
}
++answer;
markCovered(server);
}
cout << answer << '\\n';
}
return 0;
}
相关解释：这份代码使用了结构化绑定以及lambda表达式的现代C++特点。
-
结构化绑定：
-
在 markCovered 函数中：
while (!bfs.empty()) {
auto [u, distance] = bfs.front(); // ← 结构化绑定
bfs.pop();
covered[u] = true;
// …
}如果不使用结构化绑定，需要这样写：
while (!bfs.empty()) {
auto p = bfs.front(); // p 是 pair<int, int>
bfs.pop();
int u = p.first;
int distance = p.second;
// …
}
结构化绑定体现了现代C++简洁、可读性强的优点，这样的绑定不仅可以用在pair里面，而且可以结构化绑定数组，结构体，map元素，比如：
map<int, string> m = {{1, "a"}, {2, "b"}};
for (auto [key, value] : m) {
cout << key << ":" << value << endl;
}
这样的操作方便清晰绑定的元素，不用像以前一样使用first和second等成员来访问数据。
-
排序函数的lambda表达式：
sort(clients.begin(), clients.end(),
[&](int a, int b) {
return depth[a] > depth[b];
});lambda表达式由捕获列表，参数列表，返回类型和{}之中的函数体执行。捕获列表就是制定如何访问外部的变量，lambda表达式的功能相当于一个简化函数，在捕获列表之中可以指定外部变量是否可以在函数体内部可见。[&]表示引用捕获的所有外部变量，避免了拷贝带来的额外开销。
关于sort函数，他的第三个参数一般接受可调用对象，这里也就是接受lambda表达式。如果是函数或者lambda表达式在其参数列表里面接受两个形参，当函数体返回true的时候，参数列表的第一个参数应该排在第二个参数前面，在这里depth[a]更大的时候，a在前面，也就是实现了树的节点按照深度从大到小的排序。
