atcoder#AGC010C. [AGC010C] Cleaning
[AGC010C] Cleaning
Score : points
Problem Statement
There is a tree with vertices, numbered through . The -th of the edges connects vertices and .
Currently, there are stones placed on vertex . Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:
- Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices. Here, a leaf is a vertex of the tree whose degree is , and the selected leaves themselves are also considered as vertices on the path connecting them.
Note that the operation cannot be performed if there is a vertex with no stone on the path.
Constraints
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
…
:
Output
If it is possible to remove all the stones from the vertices, print YES
. Otherwise, print NO
.
5
1 2 1 1 2
2 4
5 2
3 2
1 3
YES
All the stones can be removed, as follows:
- Select vertices and . Then, there is one stone remaining on each vertex except .
- Select vertices and . Then, there is no stone on any vertex.
3
1 2 1
1 2
2 3
NO
6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6
YES