QOJ.ac

QOJ

حد الوقت: 2.0 s حد الذاكرة: 512 MB مجموع النقاط: 100 قابلة للهجوم ✓

#16793. Equidistant

الإحصائيات

在 2019 年,ICPC 区域赛的结构发生了一些变化。现在对于每个子赛区,我们需要为子赛区决赛选择一个最佳地点。为了公平起见,我们希望选择一个城市,使得所有参赛队伍到达该城市所花费的时间相同。

为了简化问题,我们假设所有队伍都将乘坐火车前往决赛。铁路系统可以表示为一棵树,其中每个城市是一个顶点,某些城市对之间由铁路连接。如果两个城市直接相连,那么从一个城市到另一个城市恰好需要一小时。

给你铁路系统的描述以及各队伍所在的城市。你需要选择一个到所有队伍所在城市距离均相等的城市,或者判断不存在这样的城市。

输入格式

第一行包含两个整数 $n$ 和 $m$,分别表示城市的数量和队伍的数量($1 \le m \le n \le 2 \cdot 10^5$)。

接下来的 $n - 1$ 行,每行包含两个整数 $v_i$ 和 $u_i$,表示第 $i$ 条铁路连接的两个城市的编号($1 \le v_i, u_i \le n$)。保证任意两个城市之间恰好有一条简单路径相连。

下一行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$,表示各队伍所在的城市($1 \le c_i \le n$)。所有队伍都位于不同的城市。

输出格式

如果无法公平地选择一个城市,输出单行 “NO”。

否则,在第一行输出 “YES”。第二行应包含一个整数,表示举办子赛区决赛的城市。如果有多个满足条件的城市,输出其中任意一个即可。

样例

输入样例 1

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

输出样例 1

YES
3

输入样例 2

2 2
1 2
1 2

输出样例 2

NO

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.