CF592D.Super M

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Ari the monster is not an ordinary monster. She is the hidden identity of Super M, the Byteforces’ superhero. Byteforces is a country that consists of n cities, connected by n - 1 bidirectional roads. Every road connects exactly two distinct cities, and the whole road system is designed in a way that one is able to go from any city to any other city using only the given roads. There are m cities being attacked by humans. So Ari... we meant Super M have to immediately go to each of the cities being attacked to scare those bad humans. Super M can pass from one city to another only using the given roads. Moreover, passing through one road takes her exactly one kron - the time unit used in Byteforces.

However, Super M is not on Byteforces now - she is attending a training camp located in a nearby country Codeforces. Fortunately, there is a special device in Codeforces that allows her to instantly teleport from Codeforces to any city of Byteforces. The way back is too long, so for the purpose of this problem teleportation is used exactly once.

You are to help Super M, by calculating the city in which she should teleport at the beginning in order to end her job in the minimum time (measured in krons). Also, provide her with this time so she can plan her way back to Codeforces.

怪兽阿里并非普通怪兽,她其实是 Byteforces 国家超级英雄——超级 M(Super M)的隐藏身份。Byteforces 由 nn 座城市组成,这些城市通过 n−1n-1 条双向道路相互连接。每条道路恰好连接两个不同的城市,且整个道路系统被设计成:任意两座城市之间均可仅通过给定道路相互到达(即该图是一棵树)。

目前有 mm 座城市正遭受人类攻击。因此,阿里……我们是说超级 M 必须立即前往每一座受攻击的城市,以震慑这些坏人。超级 M 只能通过给定的道路在城市间移动,且穿越任意一条道路恰好耗时一“克朗”(kron)——这是 Byteforces 所采用的时间单位。

然而,超级 M 当前并不在 Byteforces——她正在邻国 Codeforces 参加训练营。幸运的是,Codeforces 中有一台特殊装置,可让她瞬间从 Codeforces 传送到 Byteforces 的任意一座城市。返程路途过于遥远,因此在本题中,传送仅能使用一次。

你需要帮助超级 M,计算出她初始应传送到哪一座城市,才能使她完成全部任务所用的总时间(以克朗为单位)最短;同时,还需给出这一最短时间,以便她规划返回 Codeforces 的行程。

输入格式

The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 123456) - the number of cities in Byteforces, and the number of cities being attacked respectively.

Then follow n - 1 lines, describing the road system. Each line contains two city numbers u__i and v__i (1 ≤ u__i, v__i ≤ n) - the ends of the road i.

The last line contains m distinct integers - numbers of cities being attacked. These numbers are given in no particular order.

输入的第一行包含两个整数 nn 和 mm(1 ≤ m ≤ n ≤ 1234561 ≤ m ≤ n ≤ 123456)——分别表示 Byteforces 国家的城市总数以及正在遭受攻击的城市数量。

接下来的 n−1n-1 行描述了道路系统。每行包含两个城市编号 uiu_i 和 viv_i(1 ≤ ui, vi ≤ n1 ≤ u_i,\,v_i ≤ n)——表示第 ii 条道路所连接的两个端点城市。

最后一行包含 mm 个互不相同的整数——表示正在遭受攻击的城市编号。这些编号以任意顺序给出。

输出格式

First print the number of the city Super M should teleport to. If there are many possible optimal answers, print the one with the lowest city number.

Then print the minimum possible time needed to scare all humans in cities being attacked, measured in Krons.

Note that the correct answer is always unique.

首先输出超级 M 应该传送至的城市编号。如果存在多个可能的最优解,请输出其中城市编号最小的那个。

然后输出吓退所有受攻击城市中人类所需的最少时间(以克隆斯(Krons)为单位)。

注意:本题的正确答案始终唯一。

输入输出样例

  • 输入#1

    7 2
    1 2
    1 3
    1 4
    3 5
    3 6
    3 7
    2 7

    输出#1

    2
    3
  • 输入#2

    6 4
    1 2
    2 3
    2 4
    4 5
    4 6
    2 4 5 6

    输出#2

    2
    4

说明/提示

In the first sample, there are two possibilities to finish the Super M's job in 3 krons. They are:

and .

However, you should choose the first one as it starts in the city with the lower number.

在第一个样例中,超级 M 可以在 3 克朗内完成任务的方案有两种,它们分别是:

和 。

然而,你应该选择第一种方案,因为它起始于编号更小的城市。

输入解题思路,AI测评打分。不知道怎么写?

首页