Annual Ants' Gathering
Contest: European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1900
Tags: dfs and similar, dp, greedy, trees

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?

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

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u, v\leq 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.

Output format:
Print $$$\texttt{YES}$$$ if it is possible to gather all the ants in a single house. Otherwise, print $$$\texttt{NO}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, you can gather all the ants at house $$$3$$$ as follows:

- You tell to the ant at house $$$4$$$ to move to house $$$6$$$.
- You tell to the ant at house $$$2$$$ to move to house $$$3$$$.
- You tell to the two ants at house $$$6$$$ to move to house $$$3$$$ (which already contains two ants).
- You tell to the ant at house $$$5$$$ to move to house $$$1$$$.
- You tell to the ant at house $$$7$$$ to move to house $$$1$$$ (which already contains two ants).
- You tell to the three ants at house $$$1$$$ to move to house $$$3$$$ (which already contains four ants).

In the second sample, it is impossible to gather all the ants in a single house.

Example input:
7
5 1
3 2
4 6
3 6
7 1
1 3

Example output:
YES

Example input:
5
1 4
4 2
3 2
5 3

Example output:
NO

Editorial:
First Solution
Since ants can not move to an empty house the region of non-empty homes always needs to stay connected. Therefore, only ants on a leaf of the tree (of non-empty homes) can ever move and they can only move in one direction. Further, notice that if the smallest group of ants on a leaf can not move the solution is impossible (all other leaf groups are larger and can therefore also never be merged into the parent group of the smallest group). We can simply simulate this process.
Second Solution
Notice that the centroids of the tree are the only homes where all ants can gather up. For a fixed root we can greedily simulate the process with a DFS for each centroid.