2019牛客多校第四场A树的直径

链接：https://ac.nowcoder.com/acm/contest/884/A 来源：牛客网  

题目描述

A new city has just been built. There're nnn interesting places numbered by positive numbers from 111 to nnn.

In order to save resources, only exactly n−1n-1n−1 roads are built to connect these nnn interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述:

 

First line two positive integers, n,kn,kn,k - the number of places and persons.

For each the following n−1n-1n−1 lines, there're two integers a,ba,ba,b that stand for a road connecting place aaa and bbb. It's guaranteed that these roads connected all nnn places.

On the following line there're kkk different positive integers x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ separated by spaces. These are the numbers of places the persons are at.

输出描述:

A non-negative integer - the minimal time for persons to meet together.

示例1

输入

复制

4 2 1 2 3 1 3 4 2 4

输出

复制

2

说明

They can meet at place 1 or 3.

备注:

1≤n≤1051 \leq n \leq 10^51≤n≤105

题意：树上一些点有一个人，这些人到一个位置聚会，问你最小的最大值是多少 

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

• 必要性：这两个人要碰面，必然要走至少d/2步。

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

求解方法：树的直径，两边bfs

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 200005 using namespace std; int m,n,e,cnt,ans; struct node { int v,next,w; }edge[2*maxn]; int dis[maxn]; int vis[maxn]; int num[maxn]; int head[maxn]; void init() { memset(head,-1,sizeof(head)); cnt=0; } void addedge(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void bfs(int s) { int i; queue<int>q; memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; dis[s]=0; while(!q.empty()) {int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; int w=edge[i].w; if(!vis[v]) { if(dis[v]<dis[u]+w) { dis[v]=dis[u]+w; if(ans<dis[v]&&num[v]) { ans=dis[v]; e=v; } } vis[v]=1; q.push(v); } } } } int main() {int u,v; while(~scanf("%d%d",&n,&m)) {init(); for(int i=1;i<=n-1;i++) {scanf("%d%d",&u,&v); addedge(u,v,1); addedge(v,u,1); } while(m--) { scanf("%d",&u); num[u]=1; } bfs(1); bfs(e); printf("%d\n",(ans+1)/2); } return 0; }