Annual Ants’ Gathering

시간 제한2초메모리 제한2048 MB

요약

각 정점에 개미 한 마리씩 있는 트리에서, 개미가 더 많거나 같은 이웃으로만 이동할 수 있을 때 모든 개미를 한 집에 모을 수 있는지 판정한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Deep within a forest lies an ancient tree, home to $n$ ants living in $n$ tiny houses, indexed from $1$ to $n$ , connected by the branches of the tree.

Once a year, all the ants need to gather to watch the EUC. For this, all ants move along the $n - 1$ branches of the tree they live on to meet at the home of one ant.

However, this year the ants could not agree on where to meet and need your help to gather up. You can tell all the ants currently at house $u$ to move to house $v$ if there is a branch directly connecting those two houses. However, the ants ignore your command if there are fewer ants gathered in house $v$ than in house $u$ , i.e., if it would be easier for the ants from house $v$ to move. This even holds true if no ant at all is currently in house $v$ . You can give this kind of commands as many times as you want.

Is it possible for you to gather all the ants in a single house?

입력

The first line contains one integer $n$ ( $1 ≤ n ≤ 200\\, 000$ ) — the number of ant homes.

Each of the following $n - 1$ lines contains two integers $u$ and $v$ ( $1 ≤ u, v ≤ n$ ) — there is a branch directly connecting the house $u$ and house $v$ .

It is guaranteed that every ant can reach the house of any other ant just by following the branches of the tree.

출력

Print YES if it is possible to gather all the ants in a single house. Otherwise, print NO.

예제3

예제 1
입력
```
7
5 1
3 2
4 6
3 6
7 1
1 3
```
예상 출력
```
YES
```
예제 2
입력
```
5
1 4
4 2
3 2
5 3
```
예상 출력
```
NO
```
예제 3
입력
```
6
4 5
5 6
6 1
2 6
3 2
```
예상 출력
```
YES
```