atcoder#AGC010C. [AGC010C] Cleaning
[AGC010C] Cleaning
题目描述
頂点からなる木があり、頂点には から の番号がついています。 また、 本の辺の内、 番目の辺は頂点 と頂点 を結んでいます。
今、各頂点 には 個の石が置いてあります。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。
- 相異なる つの葉を一組選ぶ。そして、その 頂点間のパス上にある頂点全てからちょうど つ石を取り除く。
ただし、葉とは木の頂点で次数が の頂点を指し、選んだ葉自体もパス上の頂点として考える。
石が置かれていない頂点がパス上にあるときは、その操作を行えないことに注意してください。
输入格式
入力は以下の形式で標準入力から与えられる。
… :
输出格式
全ての石を取り除くことができるなら YES
を、そうでないなら NO
を出力せよ。
题目大意
一棵树,第个节点上有个石头,每次选择两个叶子节点(度数为1的节点),将路径上经过的(包括起点终点)所有节点上都取走一个石头,如果路径上有一个点上没石头这个操作就不能进行,问能不能取完所有石头。
5
1 2 1 1 2
2 4
5 2
3 2
1 3
YES
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
提示
制約
- 与えられるグラフは木である。
Sample Explanation 1
以下のようにすれば、すべての石を取り除くことができます。 - 葉として と を選ぶ。このとき、 以外の頂点に石が 個残る。 - 葉として と を選ぶ。このとき、全ての頂点から石がなくなる。