우 객 다 교meeting

링크:https://ac.nowcoder.com/acm/contest/884/A 우 객 망 
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 524288 K, 기타 언어 1048576 K 64bit IO 포맷:% 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.

제목: 한 나무 에 몇 가지 점 이 있 습 니 다. 한 가지 점 을 찾 아 이 점 에서 가장 긴 시간 을 최소 화하 고 이 시간 을 출력 합 니 다.
문제 풀이: 가장 멀리 떨 어 진 두 점 을 찾 는 것 과 같다. 시간 은 바로 이 두 점 의 거 리 를 2 로 나 누 어 정리 하 는 것 이다.
증명: 우 리 는 두 사람의 경로 와 한 개의 거 리 를 d / 2 로 조정 한 점 을 취하 여 모든 사람 을 여기 서 만 나 게 합 니 다.만약 에 한 사람 이 d / 2 시간 안에 도착 하지 못 한다 면 그것 과 경로 양쪽 에서 그것 과 먼 곳 의 거 리 는 d 보다 크 고 가장 먼 가설 과 모순 된다.
이렇게 가장 먼 한 쌍 의 점 을 찾 으 면 나 무 를 찾 는 지름 과 비슷 하 다.직접 dp 를 사용 할 수도 있 고 두 번 bfs 를 사용 할 수도 있 습 니 다. 임의의 관건 점 에서 시작 하여 가장 먼 관건 점 x 를 찾 은 다음 에 x 부터 bfs 를 찾 을 수 있 습 니 다. 새로운 가장 먼 점 과 x 가 형 성 된 것 은 바로 지름 입 니 다.

#include 

using namespace std;

const int maxn =1e5+9;
const int INF = 0x3f3f3f3f;

vectorV;

struct rt{
    int v,next;
}edge[maxn*10];

int tot;
int head[maxn];

void add_edge(int u,int v){
    edge[tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

int dis[maxn];

void bfs(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    queueque;
    que.push(s);
    while(!que.empty()){
        int u=que.front(); que.pop();
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(dis[v]==INF){
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
    int D=0,id=s;
    for(int i=0;i

ps: dp 표기 법, 사내 동료 가 쓴

#include 
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int N = 100005;
 
int Head[N];
int Next[2*N];
int V[2*N];
int tot;
int p[N];
int s[N];
int ans;
 
struct Node
{
    int id;
    int num;
};
Node M2[N][2];
 
void add(int u, int v)
{
    V[tot] = v;
    Next[tot] = Head[u];
    Head[u] = tot++;
}
 
void dfs(int u, int fa)
{
    for(int i = Head[u]; i != -1; i = Next[i])
    {
        int v = V[i];
        if(v != fa)
        {
            dfs(v, u);
            int x = 0;
            if((s[v] > 0) || p[v]) x = s[v]+1;
            if(x > M2[u][0].num)
            {
                M2[u][1] = M2[u][0];
                M2[u][0] = (Node){v, x};
            }
            else if(x > M2[u][1].num) M2[u][1] = (Node){v, x};
            s[u] = max(s[u], x);
        }
    }
}
 
void dfs2(int u, int fa, int k)
{
    ans = min(ans, max(s[u], k));
    if(k != 0) k++;
    for(int i = Head[u]; i != -1; i = Next[i])
    {
        int v = V[i];
        if(v != fa)
        {
            int a = 0;
            if(M2[u][0].id != v && M2[u][0].num != 0) a = M2[u][0].num+1;
            else if(M2[u][1].id != v && M2[u][1].num != 0) a = M2[u][1].num+1;
            if(a == 0 && p[u]) a = 1;
            a = max(a, k);
            dfs2(v, u, a);
        }
    }
}
 
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        ans = INF;
        tot = 0;
        memset(Head, -1, sizeof(Head));
        memset(p, 0, sizeof(p));
        memset(M2, 0, sizeof(M2));
        memset(s, 0, sizeof(s));
        for(int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        for(int i = 0; i < m; i++)
        {
            int x;
            scanf("%d", &x);
            p[x] = 1;
        }
        dfs(1, 0);
        dfs2(1, 0, 0);
        printf("%d
", ans);
    }
    return 0;
}