Codeforces ラウンド #245 (ディビジョン 2)D (ツリー プロパティ + 形状圧力 + dfs)_html/css_WEB-ITnose

E. Guess the Tree

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Iahub および Iahubina木々が生い茂る森へピクニックに行きました。イアハブがプログラミングで木のことを思い出すまでに 5 分もかかりませんでした。さらに、彼は新しい問題を考え出し、イアフビナはそれを解決しなければなりません。そうしないと、イアフブは彼女に食べ物を与えません

イアフブはイアフビナに尋ねます:

各内部ノード (少なくとも息子が 1 人) には少なくとも 2 人の息子がいます。

ノード i にはそのサブツリーに ci ノードがありますか?

イアフビナはツリーを推測する必要があります。賢い女の子なので、どの木もイアハブの制限に従えない可能性があることに気づきました。このようにして、イアハブは食べ物をすべて食べます。あなたは Iahubina を手伝う必要があります。Iahub の制限に従っている木が少なくとも 1 本あるかどうかを判断してください。 必要なツリーには n 個のノードが含まれている必要があります。

入力

入力の最初の行には、整数 n (1?≤?n?≤?24) が含まれます。次の行には n 個の正の整数が含まれます。i 番目の数値は ci (1?≤?ci?≤?n) を表します。

出力

少なくとも存在する場合、最初の行に "YES" (引用符なし) を出力します。 Iahub の制限に従って 1 つのツリー、それ以外の場合は "NO" (引用符なし) を出力します。

サンプル テスト

入力

出力

入力

出力

题意：RT

思路：首先注意、每个点による最少有数の点の固定会>=n/2

所以24点の状態态就减少は12点の状態态、敲好可以状態压

只考慮虑不1点，先按降序排序、その後一选孩子、如果已经轮到来选孩子、先检查它自己有能被前面的点选孩子、

如果没有选、则不要继续了、故它可能父亲了

如果选了、继续はi选2人以上の孩子、選択的点标记一下就可了

整个过程用递归算就可了