問題一覧 > 通常問題

No.1424 Ultrapalindrome

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 126
作問者 : 👑 koboshikoboshi / テスター : nok0nok0
5 ProblemId : 5100 / 出題時の順位表
問題文最終更新日: 2021-01-17 14:41:29

問題文

回文とは右から読んでも左から読んでも同じになる文章のことです。小星さんはただの回文には飽きてしまったので、あらゆる方向から読んでも同じになるような、超回文を考えることにしました。

$1$ から $N$ までの番号がついた $N$ 個の頂点をもつ木が与えられます。$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

木の頂点に文字を $1$ 文字ずつ配置します。木に文字を配置したものが超回文であるとは、次の方法で得られる文字列がすべて等しいことをいいます。

  • 次数が $1$ である異なる $2$ 頂点 $u,v$ をとり、$u$ から $v$ への最短経路を考える。この経路上の頂点に配置された文字を $u$ から $v$ に向かう順に並べて文字列を作る。

例として、以下の図のように木の頂点に文字を配置したものを考えます。次数が $1$ である頂点は $1,4,5$ であり、$u=1,v=5$ のとき得られる文字列はabe、$u=5,v=4$ のとき得られる文字列はebcdです。得られる文字列が異なっているので、これは超回文ではありません。

与えられた木の頂点に文字を $1$ 文字ずつ配置することで、超回文にすることが可能か判定してください。

入力

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
  • 入力はすべて整数
  • $2\le N\le 10^5$
  • $1\le a_i,b_i\le N$
  • 与えられるグラフは木である

出力

超回文にできるならばYes、超回文にできないならばNoと出力してください。

サンプル

サンプル1
入力
4
1 2
2 3
2 4
出力
Yes

頂点 $1,3,4$ にdを配置し、頂点 $2$ に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もしくは右上の雲マークをクリックしてアカウントを作成してください。