图片说明
图片说明

  • 题意：
  • 给出一个无向图，每条连通的点的距离都为1，
  • 给出k个点，每个点上有一个人，每个人的步行速度是1，问最短需要多少时间，所有人能走到一个点上。
  • 题解：
  • 很好就能想出来，最短时间 = 相离最远的俩个人的距离/2，向上取整。
  • 如何找这个最远的距离，用俩次bfs，这里不得不说真的很巧妙，
  • 随意找一个人所在的点，dfs，找距离这个点最远的另一个人，
  • 然后以找到的最远的那个人，再次bfs，和上面的bfs一样，找最远的第三个人。
  • 那么答案就是第二遍bfs的距离，
  • 不明白的可以在一条直线上画一下，就明白了。
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
int n,k,p,ans = 0;
int a[100010],flag[100010],sign[100010];
vector<int> v[100010];
void dfs(int x,int len)
{
  a[x] = len;
  if(sign[x] == 1 && a[x] > ans){
      ans = a[x];
      p = x;
  }
  for(int i=0;i<v[x].size();i++)
  {
      if(!flag[v[x][i]]){
          flag[v[x][i]] = 1;
          dfs(v[x][i],len+1);
      }
  }
  return ;
}
int main()
{
  int x,y;
  scanf("%d%d",&n,&k);
  for(int i=1;i<n;i++)
  {
      scanf("%d%d",&x,&y);
      v[x].push_back(y);
      v[y].push_back(x);
  }
  for(int i=1;i<=k;i++)
  {
      scanf("%d",&x);
      sign[x] = 1;
  }
  dfs(x,0);
  ans = 0;
  memset(flag,0,sizeof(flag));
  dfs(p,0);
  cout<<(ans+1)/2<<endl;
  return 0;
}