

Time Limit: 2 sec / Memory Limit: 256 MiB
配点 : 点
問題文
頂点からなる木があり、頂点には から の番号がついています。 また、 本の辺の内、 番目の辺は頂点 と頂点 を結んでいます。
今、各頂点 には 個の石が置いてあります。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。
- 相異なる つの葉を一組選ぶ。そして、その 頂点間のパス上にある頂点全てからちょうど つ石を取り除く。
ただし、葉とは木の頂点で次数が の頂点を指し、選んだ葉自体もパス上の頂点として考える。
石が置かれていない頂点がパス上にあるときは、その操作を行えないことに注意してください。
制約
- 与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
… :
出力
全ての石を取り除くことができるなら YES
を、そうでないなら NO
を出力せよ。
入力例 1Copy
5 1 2 1 1 2 2 4 5 2 3 2 1 3
出力例 1Copy
YES
以下のようにすれば、すべての石を取り除くことができます。
- 葉として と を選ぶ。このとき、 以外の頂点に石が 個残る。
- 葉として と を選ぶ。このとき、全ての頂点から石がなくなる。
入力例 2Copy
3 1 2 1 1 2 2 3
出力例 2Copy
NO
入力例 3Copy
6 3 2 2 2 2 2 1 2 2 3 1 4 1 5 4 6
出力例 3Copy
YES
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
.
Sample Input 1Copy
5 1 2 1 1 2 2 4 5 2 3 2 1 3
Sample Output 1Copy
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.
Sample Input 2Copy
3 1 2 1 1 2 2 3
Sample Output 2Copy
NO
Sample Input 3Copy
6 3 2 2 2 2 2 1 2 2 3 1 4 1 5 4 6
Sample Output 3Copy
YES