题意:有n个城市,编号从1到n,然后只有n-1条连线,就是说不会成环。从第一个地方到另一个地方只需要1秒,现在有k个人,分别分布
在不同的城市,现在问他们相聚最短所需的时间,就是说着k个人中用时最长的时间,而不是总时间。
解题思路:
就是找到最长的直径,然后取半径。
先在这k个人中任选一个人,就是这个人所在的城市a。这n个城市组成一个图,然后从这个城市a深搜找到k个城市中离该城市最远的城市b,
然后再以b城市为根深搜一次,找到k个城市中离b城市最远的城市c,此时b 到c就是直径,然后再向上取整。
向上取整:3.2 变为4
向下取整 3.2变为3
该题也可以用广搜。
答案
#include <bits/stdc++.h>
using namespace std;
typedef longlong ll;
const int MAX_N = 1e5+7;
int vis[MAX_N];
int n, k, s, ans;
vector<int> G[MAX_N];
void dfs(int x,int pre,int num){
if(vis[x]&&ans<num){
ans=num;
s=x;
}
for(int i = 0;i<G[x].size();i++){
int u=G[x][i];//相邻的点
if(u!=pre)//防止成环
dfs(u,x,num+1);//x是u的上一个点
}
}
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);//这里0的含义就是x点的上一个点0 ,并让0为根,num=1,是答案直接/2,就不需要向上 取整了
dfs(s,0,1);
printf("%d",ans/2);
return0;
}