2019牛客暑期多校训练营（第四场）A-meeting（树的直径）

>传送门<

题意：n给城市有n-1条路相连，每两个城市之间的道路花费为1，有k个人在k个城市，问这k个人聚集在同一个城市的最小花费

思路：（官方给的题解写的挺好理解的）

考虑距离最远的两个关键点，设它们的距离为d，d/2上取整即为答案。

• 必要性：这两个人要碰面，必然要走至少d/2步。
• 充分性：我们取两人路径中和一头距离为d/2上取整的一个点，让所有人在这相聚。如 果有一个人在d/2时间内到不了，那么它和路径两头中与它远的那一头的距离大于d，与 最远的假设矛盾。

找到这样最远的一对点类似找树的直径。可以直接dp，也可以采用两遍dfs：

从任意一个关键点开始，找到离它最远的关键点x，再从x开始dfs，找到的新的最远点和x形成的就是直径。

当然对着题面直接dp也是可以做的，但是比较难写。

Code

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int MAX_N = 1e5+7;
 
int n, k, s, ans;
int vis[MAX_N];
vector<int> G[MAX_N];
 
void dfs(int u, int pre, int step)
{
    if(vis[u]&&ans<step) ans = step, s = u;
    //或者用auto v: G[u]
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v!=pre) dfs(v, u, step+1);
    }
}
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int x;
    for(int i = 1; i <= k; i++) 
        cin>>x, vis[x] = 1;
    dfs(x, 0, 1);
    dfs(s, 0, 1); //初始step为1，就相当于最后ans向上取整了 
    cout << ans/2;
    return 0;
}