← 返回题目列表

Codeforces · 1949/C

C. 一年一度的蚂蚁聚会

中文机器翻译题面 查看原题

森林深处有一棵古树,里面有 $$$n$$$ 蚂蚁,住在 $$$n$$$ 个小房子里,索引从 $$$1$$$ 到 $$$n$$$,由树枝连接。

每年一次,所有的蚂蚁都需要聚集在一起观看 EUC。为此,所有蚂蚁都会沿着它们所居住的树的 $$$n-1$$$ 树枝移动,并在一只蚂蚁的家中相遇。

然而,今年蚂蚁们无法就集合地点达成一致,需要你的帮助来集合。如果有一根分支直接连接 $$$u$$$ 房子里的所有蚂蚁,你可以告诉 $$$u$$$ 房子里的所有蚂蚁搬到 $$$v$$$ 房子。然而,如果 $$$v$$$ 房子里聚集的蚂蚁比 $$$u$$$ 房子里聚集的蚂蚁少,也就是说,如果 $$$v$$$ 房子里的蚂蚁更容易移动,蚂蚁就会忽略你的命令。如果当前房子里根本没有蚂蚁$$$v$$$,这甚至也成立。您可以根据需要多次发出此类命令。

你有可能将所有蚂蚁聚集在一个房子里吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 200\,000$$$) — 蚂蚁家园的数量。

以下 $$$n-1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v\leq n$$$) — 有一个分支直接连接房屋 $$$u$$$ 和房屋 $$$v$$$。保证每只蚂蚁只要沿着树枝就可以到达任何其他蚂蚁的房子。

输出

如果可以将所有蚂蚁聚集在一个房子里,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。

示例

输入 #1

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

输出 #1

YES

输入 #2

5
1 4
4 2
3 2
5 3

输出 #2

NO

输入 #3

6
4 5
5 6
6 1
2 6
3 2

输出 #3

YES

注意

在第一个示例中,您可以收集 $$$3$$$ 房子里的所有蚂蚁,如下所示:

- 你告诉 $$$4$$$ 房子里的蚂蚁搬到 $$$6$$$ 房子。
- 你告诉 $$$2$$$ 房子里的蚂蚁搬到 $$$3$$$ 房子。
- 你告诉 $$$6$$$ 房子里的两只蚂蚁搬到 $$$3$$$ 房子(里面已经有两只蚂蚁)。
- 你告诉 $$$5$$$ 房子里的蚂蚁搬到 $$$1$$$ 房子。
- 你告诉 $$$7$$$ 房子里的蚂蚁搬到 $$$1$$$ 房子(里面已经有两只蚂蚁)。
- 你告诉 $$$1$$$ 房子里的三只蚂蚁搬到 $$$3$$$ 房子(里面已经有四只蚂蚁)。

在第二个样本中,不可能将所有蚂蚁聚集在一个房子里。