Minimum Maximum Distance
传送门
You have a tree with n n n vertices, some of which are marked. A tree is a connected undirected graph without cycles.
Let f i f_i fi denote the maximum distance from vertex i i i to any of the marked vertices.
Your task is to find the minimum value of f i f_i fi among all vertices.
For example, in the tree shown in the example, vertices 2 2 2, 6 6 6, and 7 7 7 are marked. Then the array f ( i ) = [ 2 , 3 , 2 , 4 , 4 , 3 , 3 ] f(i) = [2, 3, 2, 4, 4, 3, 3] f(i)=[2,3,2,4,4,3,3]. The minimum f i f_i fi is for vertices 1 1 1 and 3 3 3.
Input
The first line contains an integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and k k k ( 1 ≤ k ≤ n ≤ 2 ⋅ 1 0 5 1 \le k \le n \le 2 \cdot 10^5 1≤k≤n≤2⋅105) — the number of vertices in the tree and the number of marked vertices, respectively.
The second line of each test case contains k k k integers a i a_i ai ( 1 ≤ a i ≤ n , a i − 1 ≤ a i 1 \le a_i \le n, a_{i-1} \le a_i 1≤ai≤n,ai−1≤ai) — the indices of the marked vertices.
The next n − 1 n - 1 n−1 lines contain two integers u i u_i ui and v i v_i vi — the indices of vertices connected by the i i i-th edge.
It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, output a single integer — the minimum value of f i f_i fi among all vertices.
Examples
input #1
6
7 3
2 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 2 3 4
1 2
2 3
3 4
5 1
1
1 2
1 3
1 4
1 5
5 2
4 5
1 2
2 3
1 4
4 5
10 8
1 2 3 4 5 8 9 10
2 10
10 5
5 3
3 1
1 7
7 4
4 9
8 9
6 1
10 9
1 2 4 5 6 7 8 9 10
1 3
3 9
9 4
4 10
10 6
6 7
7 2
2 5
5 8
output #1
2
2
0
1
4
5
input #2
3
6 1
3
1 2
1 3
3 4
3 5
2 6
5 3
1 2 5
1 2
1 3
2 4
3 5
7 1
2
3 2
2 6
6 1
5 6
7 6
4 5
output #2
0
2
0
题目翻译
你有一棵树，树上有 n n n 个顶点，其中一些顶点被做了标记。树是没有循环的连通无向图。
让 f i f_i fi 表示顶点 i i i 到任何一个有标记顶点的最大距离。
你的任务是找出所有顶点中 f i f_i fi 的最小值。
例如，在示例所示的树中，顶点 2 2 2 、 6 6 6 和 7 7 7 已被标记。然后是数组 f ( i ) = [ 2 , 3 , 2 , 4 , 4 , 3 , 3 ] f(i) = [2, 3, 2, 4, 4, 3, 3] f(i)=[2,3,2,4,4,3,3] 。顶点 1 1 1 和 3 3 3 的最小值 f i f_i fi 。
输入格式
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104 ) - 测试用例的数量。
每个测试用例的第一行包含两个整数 n n n 和 k k k （ 1 ≤ k ≤ n ≤ 2 ⋅ 1 0 5 1 \le k \le n \le 2 \cdot 10^5 1≤k≤n≤2⋅105 ）–分别是树中的顶点数和标记顶点数。
每个测试用例的第二行包含 k k k 个整数 a i a_i ai ( 1 ≤ a i ≤ n , a i − 1 ≤ a i 1 \le a_i \le n, a_{i-1} \le a_i 1≤ai≤n,ai−1≤ai ) - 标记顶点的索引。
接下来的 n − 1 n - 1 n−1 行包含两个整数 u i u_i ui 和 v i v_i vi --由 i i i /th边连接的顶点的索引。
保证所有测试用例的 n n n 之和不超过 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105 。
输出格式
对于每个测试用例，输出一个整数，即所有顶点中 f i f_i fi 的最小值。
以上来自 C o d e F o r c e s ，翻译： D e e p L 以上来自CodeForces，翻译：DeepL 以上来自CodeForces，翻译：DeepL
解题思路
前置知识
- 树的直径。
正文
用手（<-你自己的），拿好可以在粗糙物体表面留下痕迹的棍状物体，在一粗糙平面模拟样例（简单来说就是手动模拟样例）可以发现一个性质：这两个点都是红点间的路径上的，且最后的答案就是最大的红点间的间距的长度除以二上取整。
所以正解思路就为：找出最大的红点间的间距，再除以二向上取整。
暴力枚举复杂度为 O ( n 2 ) O(n^2) O(n2)，显然不可行。
找到间距可以参考求树的直径的方法，两遍 D F S DFS DFS 即可。时间复杂度 O ( n ) O(n) O(n)。
注意：当树上只有一个标记点时，答案为 0 0 0，要直接特判输出，不然会出问题（血淋淋的痛啊）。文章来源：https://www.toymoban.com/news/detail-836961.html
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 2e5 + 5;
int n, k, a[Maxn];
int vis[Maxn], f[Maxn], dis[Maxn];
vector<int> e[Maxn];
int ans;
inline void dfs1(int x, int fa);
inline void dfs2(int x, int fa);
inline void solve();
inline void work() {
int T;
cin >> T;
while (T--)solve();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
work();
return 0;
}
inline void dfs1(int x, int fa) {
if (fa != -1)f[x] = f[fa] + 1;
for (auto i : e[x]) {
if (i == fa)continue;
dfs1(i, x);
}
}
inline void dfs2(int x, int fa) {
if (fa != -1)dis[x] = dis[fa] + 1;
for (auto i : e[x]) {
if (i == fa)continue;
dfs2(i, x);
}
}
inline void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++)e[i].clear(), dis[i] = f[i] = a[i] = 0;
for (int i = 1; i <= k; i++)cin >> a[i];
int u, v;
for (int i = 1; i <= n - 1; i++)cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
if (k == 1) {
cout << 0 << endl;
return;
}
f[0] = -1, dis[0] = -1, dfs1(1, -1), ans = a[1];
for (int i = 1; i <= k; i++)if (f[a[i]] > f[ans])ans = a[i];
dfs2(ans, -1), ans = a[1];
for (int i = 1; i <= k; i++)if (dis[a[i]] > dis[ans])ans = a[i];
cout << (dis[ans] + 1) / 2 << endl;
}
洛谷评级： 普及 / 提高 − \textcolor{orange}{普及/提高−} 普及/提高−，适合新手宝宝体质哦（颖音）。文章来源地址https://www.toymoban.com/news/detail-836961.html
到了这里，关于CF1881F Minimum Maximum Distance 题解 贪心+DFS的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
