atcoder.jp 公式解説とは違う方法らしい。 解法 この問題は、頂点 $ U_i $の子要素で根からの距離が $ D_i $である頂点はいくつか、というクエリに回答せよ、と言い換えられる。 複数のクエリに回答する問題 複数のクエリに回答する問題は、次のような解法パ…

atcoder.jp 解法 N!の約数を順に列挙していこうとすると、N次第ではN!がとてつもなく大きい数になってしまうため、現実的ではない。 そこで、約数を素因数を組み合わせた結果と考えることにする。 具体的には、1 ~ Nまでの数をそれぞれ素因数分解し、それぞ…

atcoder.jp 解法 木上のDFSを理解していますか？って感じの問題。 訪れていない都市を優先的に移動を繰り返すということで、深さ優先探索と同じ方法であることがわかる。 訪れていない都市がない時、元の都市に戻るという動作もDFSそのままだ。 いまいる都市…

問題へのリンク 解法 最短経路を求めたりする問題ではないので、BFSではなくDFSがしたい気分になる。 制約がとても緩いので、全探索が有効そう。 スタート地点は最大でも16通りしかないので、すべてのスタート地点から探索を開始してみることにする。 DFSの…