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

时间限制：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 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

题目大意：给你n个点，n-1条边，及m个人所在的点，问这m个人最少需要多少时间才能同时见面，同时走！

题目思路：首先，对这个图进行分析，n个点，exactly(n-1)条边，那么给你就是一颗树，我们先假设给的树是一条直线：

1--->2---->3 ，那么这三个点的人相见的时候的时间就是，(最远的两点距离+1)/2，这是百分百可以确定的。然后我们再看一般情况： 

假设  A C E 我们看其汇聚最短多少时间，我们可以枚举A,C,E 作为起点与其他两个汇聚的时间，我们发现 时间即为两个相聚最远的点相聚的时间，其实也不难理解因为两个最远其余的点一定比这两个早汇合，可以想想直线情况。比如 这个例子 A C 最远所以应该在B 点回合  时间为2

所以现在题目就转换成为了，在一棵树中求k个点中，任意两点距离的最大值，这个最大值有一个概念，叫做树的直径，所谓树的直径就是 树中距离最大的两点之间的距离。树的直径求法：

第一步：任取一个点P为起点，找到与其距离最远的点Q。

第二步：以Q为起点，找到与其最远的点W  Q-W之间的距离即为 树的直径。

证明可以画两条 相交的直线证明，这里不在解释。

还有一个细节：怎么找出k个点组成的树的直径，我们只需要找的时候，只标记在k个点中的点就可以了，其余的点不处理。在k个点中筛选。

具体实现步骤就可以用 两边DFS就可以了，因为这是树复杂度也不可能太大，所以直接深搜：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e5+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
int head[maxn];
bool vis[maxn];
bool pos[maxn];
ll dis[maxn];
struct node{
    int e,next;
    ll w;
}edge[maxn];
ll cnt=0;
ll x[maxn];
void addedge(ll u,ll v,ll w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
    edge[cnt]=node{u,head[v],w};
    head[v]=cnt++;
}
void dfs(ll s)
{
    vis[s]=true;
    for(int i=head[s];i!=-1;i=edge[i].next)
    {
        int e=edge[i].e;
        if(!vis[e])
        {
            dis[e]=dis[s]+1;
            dfs(e);
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        addedge(x,y,1);
    }
    for(int i=1;i<=m;i++) {scanf("%lld",&x[i]);pos[x[i]]=true;}
    dfs(x[1]);
    ll z=-1,maxl=-INF;
    for(int i=1;i<=n;i++)
            if(pos[i]&&dis[i]>maxl)
            {
                z=i;
                maxl=dis[i];
            }
    dis[z]=0;
    for(int i=1;i<=n;i++) vis[i]=false;
    maxl=-INF;
    dfs(z);
    for(int i=1;i<=n;i++)
            if(pos[i]&&dis[i]>maxl)
                maxl=dis[i];
    printf("%lld\n",(maxl+1)/2);
    return 0;
}

总结：

1.了解了树的直径,图论的问题和概念还需要进一步扩充。

1.端正心态，继续加油！