No.1424 Ultrapalindrome
問題文最終更新日: 2022-04-25 23:56:23
問題文
回文とは右から読んでも左から読んでも同じになる文章のことです。小星さんはただの回文には飽きてしまったので、あらゆる方向から読んでも同じになるような、超回文を考えることにしました。
から までの番号がついた 個の頂点をもつ木が与えられます。 番目の辺は頂点 と頂点 を結んでいます。
木の頂点に文字を 文字ずつ配置します。木に文字を配置したものが超回文であるとは、次の方法で得られる文字列がすべて等しいことをいいます。
- 次数が である異なる 頂点 をとり、 から への最短経路を考える。この経路上の頂点に配置された文字を から に向かう順に並べて文字列を作る。
例として、以下の図のように木の頂点に文字を配置したものを考えます。次数が である頂点は であり、 のとき得られる文字列はabe
、 のとき得られる文字列はebcd
です。得られる文字列が異なっているので、これは超回文ではありません。
与えられた木の頂点に文字を 文字ずつ配置することで、超回文にすることが可能か判定してください。
入力
- 入力はすべて整数
- 与えられるグラフは木である
出力
超回文にできるならばYes
、超回文にできないならばNo
と出力してください。
サンプル
サンプル1
入力
4 1 2 2 3 2 4
出力
Yes
頂点 にd
を配置し、頂点 にa
を配置することで、問題文中の方法で得られる文字列がすべてdad
になります。ゆえにこれは超回文です。
サンプル2
入力
6 1 3 2 3 3 4 3 6 4 5
出力
No
どのように文字を配置しても超回文にできません。
サンプル3
入力
7 1 2 2 3 3 4 4 5 5 6 6 7
出力
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。