AtCoder 第二回全国統一プログラミング王決定戦予選 B - Counting of Trees （再解説） (Go)
irisruneです。前回扱った問題のアルゴリズム面についてもう少し解説したいと思います。
問題リンクと提出コードは前回記事を参照してください。
例えば以下のような入力について考えます。
6 0 1 1 2 2 3
すると、次のような木は条件を満たします。
ここで他にどのような木が条件を満たすかについて考えると、頂点1を根として頂点1から距離が短い順番に見ることで以下のように考えられます。
- 頂点1との距離が0の頂点の配置は1通りである。
- 頂点1との距離が0の頂点は頂点1ただ1つのみ存在することが木の存在条件である。
- 頂点1との距離が1の頂点の親は頂点1以外あり得ないので、配置は1通りである。
- 頂点1との距離が2の頂点は頂点1との距離が1の頂点を親に持つことができるため、配置は2通りである。
- 頂点1との距離が2の頂点は2つ存在するため、それぞれ2通りとなり全体で4通りとなる。
- 頂点1との距離が3の頂点は頂点1との距離が2の頂点を親に持つことができるため、配置は2通りである。
以上より、各頂点について親となる頂点の候補の数（頂点1との距離が自身より1小さい頂点の数）がそれぞれの頂点の配置のパターン数となるため、全頂点についてその積をとれば答えを求めることができます。
雑記
- ここしばらく忙しいのもあり、過去問を扱うことになるかもしれません。
