链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 524288K，其他语言1048576K

64bit IO Format: %lld

题目描述

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 21 23 13 42 4

输出

2

说明

They can meet at place 1 or 3. 1<=n<=1e5 题意 给出一颗树和一些点,一个点到另一个点的距离为1,求这些点在树上最大距离的一半 思路 要求图上的最大距离可先任意取一个点求最大距离,再从最大距离的这个点再找一次最大距离(因为重新求的最大距离必定大于或等于原先的最大距离) 这里求最大距离用了边权取负再dijkstra,把求出的最小负距离取反就得到最大正距离 代码

1 #include
          
            2 using namespace std; 3 const int amn=2e5+5,inf=0x3f3f3f3f; 4 int n,k,dis[amn]; 5 int p[amn]; 6 struct node{ 7     int pos,val; 8     bool operator <(const node &a)const {
        return a.val
           
             que;14 int head[amn],edgenum=0,vis[amn];15 void add(int f,int t,int co)16     {17         e[++edgenum].next=head[f];18         head[f]=edgenum;19         e[edgenum].to=t;20         e[edgenum].w=co;21     }22 void Dijkstra(int s)23     {24         memset(dis,0x3f,sizeof(dis));25         memset(vis,0,sizeof vis);26         while(que.size())que.pop();27         dis[s]=0;28         node a;29         a.pos=s,a.val=dis[s];30         que.push(a);31         while(!que.empty())32             {33                 node x=que.top();que.pop();34                 int u = x.pos;35                 if(x.val > dis[u]) continue;36                 vis[u]=true;37                 for(int i=head[u];i!=-1;i=e[i].next)38                     {39                         int v=e[i].to;40                         if(vis[v])    continue;41                         if(dis[v]>e[i].w+dis[u])42                             {43                                 dis[v]=e[i].w + dis[u];44                                 a.pos=v,a.val=dis[v];45                                 que.push(a);46                             }47                     }48             }49     }50 int main(){51     memset(head,-1,sizeof head);52     ios::sync_with_stdio(0);53     cin>>n>>k;54     int u,v,ans;55     for(int i=1;i
            
             >u>>v;57         add(u,v,-1);58         add(v,u,-1);59     }60     for(int i=1;i<=k;i++){61         cin>>p[i];62     }63     Dijkstra(p[1]);64     int maxn=inf,maxi=0;65     for(int i=1;i<=k;i++){66         if(dis[p[i]]