木dpから全方位木dpへの発展【競技プログラミング】

# はじめに
- 以前、[木dpをやっつけた](https://qiita.com/kei_tnk/items/bf2165a09c741e900391)ことがあったけど、今度は全方位木dpが現れたよ...ボスケテ...
- まぁ、やるしかないので、やっつけます。
- そう言えば最近の投稿では特に宣言してなかったけど、『使用言語はswiftです』。c++やpythonの人には申し訳ないです。

# 対戦相手
- [コイツ](https://atcoder.jp/contests/dp/tasks/dp_v)です。
- まず、頂点数N、辺数N-1の木が用意されます。
- 各頂点は白または黒を塗ることが出来ます。
    - 黒の頂点同士は全て連結させる必要があります。
        - 黒の頂点が一つだけも可です。
- 各頂点(0..<N)を黒とする場合の数を、各頂点毎に答えなさい。答えはmod Mとします。
```
3 100 // 頂点数3、mod 100
1 2 // 辺①1-2 、0-idxなら 0-1
2 3 // 辺②2-3 、0-idxなら 1-2
```
- 各頂点毎の木dpでイケちゃえば、何の苦労もないけど、前回も今回も、制約上、Nの最大値は$10^5$個。前回は一つの頂点に対して木dpを行って、150ms程度だったよ。で、今回、この木dpを各頂点ごとに行ったら更にN倍になるから、余裕で2000msを超えるよね。

# TLE覚悟で、普通の木dpで解いてみる
- 倒れるときは、前のめり!...と言うことで、駄目と分かっていても解くね。
```swift
extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var G = [[Int]](N,[])
for _ in 0..<N-1 {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    G[a] += [b]
    G[b] += [a]
}

// 頂点iを根とする部分木における解（場合の数）を格納する配列。
let dp0 = [Int](N,1) // 最低でも自身だけを頂点とする場合の数があるから初期値を1
var dp = dp0

// 頂点iを根とする部分木における解（場合の数）をdp[i]に格納する再帰関数。
// どちらの方向に真の根が有るかの情報として、親ノードも引数としている。
func dfs(_ node: Int, _ parent: Int) {
    for v in G[node] { // 頂点(vertex)よりv
        if v == parent { // 親方向には向かわない
            continue
        }
        dfs(v, node) // 自らを親に指定
        dp[node] *= (dp[v] + 1) // vの頂点が黒の場合の数dp[v]と白の場合の数1
        dp[node] %= M
    }
    return
}

for v in 0..<N {
    dfs(v,-1)
    print(dp[v])
    dp = dp0 // リセット
}
```
- ここまでは、[前回の木dp](https://qiita.com/kei_tnk/items/bf2165a09c741e900391)の手法でイケたね。
- あぁ、提出結果はもちろんTLEです。

# 無駄にあがいてみた
- メモ化でdp計算結果を使い回すことで計算量削減できないかな？と思ってあがいたのが次のコード
```swift
extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

let (N,m) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let M = Int32(m) // Int32化
var G = [[Int]](N,[])
for _ in 0..<N-1 {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    G[a] += [b]
    G[b] += [a]
}

// dpをメモ化により使い回し可とする。
// dp[i][j]を頂点jを親とする頂点iを部分木頂点とする解（場合の数）を格納する配列とする。
var dp = [[Int32]](N,N,-1) // メモ化配列


// 配列dp[i][j]の解を格納する再帰関数
// どちらの方向に真の根が有るかの情報として、親ノードも引数としている。
func dfs(_ node: Int, _ parent: Int) {
    if dp[node][parent] != -1 {
        return // 回答済みなら何もしない
    } else {
        dp[node][parent] = 1 // 未回答なら、初期値を1としてスタート
    }
    
    for v in G[node] { // 頂点(vertex)よりv
        if v == parent { // 親方向には向かわない
            continue
        }
        dfs(v, node) // 自らを親に指定
        dp[node][parent] *= (dp[v][node] + 1)// vの頂点が黒の場合の数dp[v]と白の場合の数1
        dp[node][parent] %= M
    }
 
    return
}

for v in 0..<N {
    dfs(v,v) // 自分が根であるときの格納場所をdp[v][v]とする
    print(dp[v][v])
}
```
- まぁ、駄目でした。REとTLEが出まくりです。最初の6問のみAC。
- 上記コードは、dpをInt32型にして少しでもメモリを減らしたから、TLEもでたけど、dpをInt型で設定したときは、TLEじゃなく、殆どREでした。
- 縦N×横Nの二次元配列dpで、$N=10^5$は厳しいっていうのを見つけて諦めました。知らなかったです。
    - でも、メモリ不足なら、MLEが出るはずだし、REが出たケースの中にメモリが50MB程度で、限度内のものもあったんだよね。少し調べたら、スタックオーバーフローだと、MLEじゃなく、REになるみたい。まぁ、スタックオーバーフローなんて、名前は聞いたことあるけど、意味は分かってないです。
- とりあえず、ギブアップ。REとなるデータケースは、全て1MB程度の入力データだから、paiza.ioの入力に使えないからお手上げ。そのうち、VScodeでswiftを動かせる環境を作ったら、確認します。REをクリアしてもTLEも出てるし、素直に、全方位木dpに向かいます。
- ちなみに、[TLEが出るケースについて分析している方](https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e#%E7%B5%90%E6%9E%9C%E3%81%AE%E3%83%A1%E3%83%A2%E5%8C%96)がいました。一つの頂点に多数の辺が接続しているとき（スターグラフと呼ぶ）でアウトみたいです。なるほど、勉強になります！

# 全方位木dpとは？
- 「全方位木」を使ったdpではなく、全方位の「木dp」って意味みたい。
- で、いろいろな人達の解説を見て、概ね理解したよ。
- まず、手順について結論から言います。考えるんじゃない、感じるんだ！
    - ①最初に、適当な頂点vを決めて、木dpをして、頂点vの答えを出します。コレは再帰関数を使うから、実体は深さ優先探索だね。
        - 計算量がシビアじゃなければ、vは頂点1(0-idxなら、頂点0)の決め打ちで良いね。
    - ②次に、頂点vから、幅優先探索で、各頂点の答えを出していきます。
- 図で書いた方が分かり易いね。昨日、ipad miniとapple pencilを買ったから、活用しちゃうよ！
- 最初は頂点vを根とした木dpを行います。この時の情報の流れを赤矢印で示します。
![スクリーンショット 0006-11-03 19.23.36.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/5f9e7c68-d226-7465-3280-3f95d2b07cb1.jpeg)
- この時、頂点vは解答の情報を持っているのは、ご承知のとおりです。
- 次に、頂点vから情報を下ろしていきます。下ろしていく矢印を紫色にしています。これは、幅優先探索で下ろします。
![スクリーンショット 0006-11-03 19.32.51.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/fefba032-6698-5090-a0c5-88ce0e531aeb.jpeg)
- 頂点1,2,3の答えも固まります。部分木の時の答えは、dp[i]に格納していましたが、ここで、解答を格納する配列としてans[i]を考えて、当初の想定通り、v=0として考えると、以下のとおりです。
    - ans[0] = dp[0]です。まぁ、これは良いよね。つぎは、データを下ろした頂点達です。
        - ans[1] = dp[1] * (ans[0] / (dp[1] + 1) + 1) -- これもまぁ、分かるよね。dpの時と似てるよね。
        - ans[2] = dp[2] * (ans[0] / (dp[2] + 1) + 1)
        - ans[3]...もういいでしょ？こんな流れです。
- 上記の図を見て分かるとおり、各頂点に繋がっている各辺において、各頂点に向かう矢印が全て刺さったとき、解が出ます。例えば、頂点2については、3本の辺があるけど、上図において、矢印が3本(赤2本、紫1本)刺さっているよね。
- 全ての辺で両方向の矢印がそろったとき、全ての頂点で答えがそろうことになります。
- よって、このやり方だと、最初のdp埋め過程で(N-1)、戻しのans埋め過程で(N-1)だから、合計の計算量は(N-1)×2になる！やったね！
- この全方位木dpって、英語で表現すると、ReRootingっていうみたい。なんだか、そっちの方が作業イメージに合ってるね。
- 幅優先探索(breadth-first search)については、[昔やったコレ](https://qiita.com/kei_tnk/items/222eb21227c08494054f)で復習します。

# 上記方針に基づいて全方位木dpをコードにする
- 駄目でした！
- なんの成果も!! 得られませんでした!!（号泣）
- 前項でぇ、偉そうにぃ、`ans[1] = dp[1] * (ans[0] / (dp[1] + 1) + 1) -- これもまぁ、分かるよね。dpの時と似てるよね。`とか書いてるじゃないですかぁ。
- コレ駄目ですわ。 __dpやansがmod計算されてんのに割り算とかしちゃアカンですわ__ 。詳しくは[コチラ](https://qiita.com/kei_tnk/items/8d727a6eed29ee796908)。
- じゃあ、どうやって、ans[1]を出せば良いの？
    - 「ans[0]とdp[1]の組み合わせ」は割り算が出てくるから駄目だよね。
    - まぁ、ans[0]の代わりに「dp[2]とdp[3]の組み合わせ」を使うなら、乗算だけでイケるね。
        - ans[1] = dp[1] * ( (dp[2] + 1) * (dp[3] + 1) + 1) 
        - でも、これって、結局、計算量が爆発しそうね。
- 諦めた！やっぱり、全方位木dpを理論的な基礎からやり直そう！

# 全方位木dpの理論的な理解 - その1 (木dpへのモノイド導入)
- いったん、具体的な問題から離れます。
- けんちょんさんの解説に基づく全方位木dpのアルゴリズムを僕なりに噛み砕いて解説します。

https://drken1215.hatenablog.com/entry/2024/04/15/135700

![](https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20240408/20240408105019.png)
- まず、全方位木dpの話に入る前に、部分木に関する木dpの話をします。
- 例えば、上図例で頂点2を根として、頂点5の部分木dpを考えます。
- dpは以下のとおり考える。
- 頂点vに対し、初期値e(加算計算なら0，乗算計算なら1),頂点vの子cldrn[0],cldrn[1],...がいる前提として、下記のコードが成立するものと考えます。v=5なら、cldrn = [7,9]になるよね。
```swift
dp[v] = e // mergeが加算計算なら0、乗算計算なら1
for cld in cldrn {
    dp[v] = merge(dp[v],dp[cld])
}
dp[v] = sefloperation(v,dp[v])
```
- 上記のmergeは別途設定する関数になります。
    - ちょっと数学的な話をしちゃうね。
    - [モノイド](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89)の組 (S, •, e)と上記dp計算の対比をするね。
    - 「S」は配列dp、「･」は関数merge、「e」はe（eは単位元と呼ぶ）となります。
- 続いて、selfoperationってなんじゃい！って感じだよね。、cldの情報だけでなく、cld以外の情報（通常、自ノードに紐付いた情報）も使って答えを出すのに必要な関数です。この作業を行う関数をselfoperationと名付けました。
    - あれ？mergeがモノイドの結合「・」だったけど、selfoperationって、モノイドの何？って思った人いるよね？
        - ...細けぇ事はいいんだよ！適当なこと言えば、写像とでも思っておけばいいんじゃね？（なげやり）
- ここまでは、[学習済み](https://qiita.com/kei_tnk/items/bf2165a09c741e900391)の部分木に関する木dpをモノイドの概念を使って解く場合の整理です。
- 実はここまで、全方位木dpの説明は全くしてません(キリッ)

# 全方位木dpの理論的な理解 - その2 (dpの2次元化)
- で、ここから全方位木dpの説明を始めるよ。さっきと同じ図を再掲示します。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20240408/20240408105019.png)
- ポイント！
    - 普通の木dpでは木全体の根は固定でした。そして、例えば、根を頂点2と考えたとき、頂点5の部分木dpとして存在するのはdp[5]一つだけでした。
    - しかし、全方位木dpでは根が固定されないため、dp[5]を一つの値としてしまうと、頂点9を根とした場合の部分木としてのdpに使えません。よって、dp[5]をたった一つの値にすることを諦めます。
    - 答えを先に書いちゃうと2次元化します。
- さて、基本に立ち返って、dp[5]はどうやって算出したでしょうか？
```swift
dp[v] = e // mergeが加算計算なら0、乗算計算なら1
for cld in cldrn { // v=5なら、cldrn = [7,9]
    dp[v] = merge(dp[v],dp[cld])
}
dp[v] = sefloperation(v,dp[v])
```
- 頂点5について、頂点7,9のdpを使って計算してるね。
- もし、頂点7,9と同様に、頂点2からもdpを取得できれば、頂点5を木全体の根として計算出来るね。
- そこで、頂点2について、頂点5を親とする部分木のdpをdp[5][頂点2]と表現とするのはどうだろうか？
    - すると、頂点5に隣接する部分木のdp3つはdp[5][頂点2]、dp[5][頂点9]、dp[5][頂点7]と表現できるね。
    - ここで、頂点5と繋がっている3つの頂点は、グラフ配列G[5]に格納されてる事を踏まえると...
    - 3つの頂点について全て作業したいときは、`for c in G[5] {dp[5][c]に関する何かの処理}`と書けば良いね。
    - つまり、コレまで、dp[5]として、頂点5の部分木としての値を保持していたけど、今後は、自らを根とする場合も考慮し、dp[5][頂点2]、dp[5][頂点9]、dp[5][頂点7]と分解した形で保持することとする。
    - ほら、これが、dpの二次元化です。
        - 言うまでもないけど、dpは二次元配列だけど、縦N×横Nみたいな配列じゃないよ。
        - dp[5].count=3だけど、dp[1].count=2、dp[10].count=1だよ。不揃いの林檎だよ！(ネタが古くてスマヌ)

# 全方位木dpの理論的な理解 - その3 (部分木dpの埋め処理)
- ここでは、また部分木の木dpの説明をするよ。さっきと同じ図を再掲示します。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20240408/20240408105019.png)
- dpを二次元化したら、再帰関数rec_cは以下のように書きます。
    - ちなみに、この段階では部分木dpだから、仮に木全体の根を頂点0とした場合、dp[5][頂点2]は計算されず、dp[5][頂点7]とdp[5][頂点9]だけ計算されます。
```swift
    func rec_c(_ v: Int, _ p: Int) -> Int {
        let gv = G[v]
        var ans = e
        dp[v] = [Int](gv.count,e)
        for i in 0..<gv.count {
            let c = G[v][i] // childのcにしました。
            if c == p { continue }
            dp[v][i] = rec_c(c, v) // slfop適用済みの値が各dp[v][i]に格納
            ans = mrg(ans, dp[v][i]) // この時点ではマージしてるだけ
        }
        return slfop(v, ans) // マージした結果にslfopを適用
    }
```
- 上記で関数名を短縮化してます。mrg(←merge)、slfop(←selfoperation)。長い関数名って打ちづらいから好きじゃないんだよね。
- 繰り返しになるけど、これは部分木の木dpなので、`rec_c(0,-1)`を実行しても、dp[2][頂点5]は計算されるけど、dp[5][頂点2]は計算されません。
- あ、今回、再帰関数の名前をrec_cにしたけど、子に向かう方向（dp[v][vの子])だけdpが埋まるため、childのcを付けました。

# 全方位木dpの理論的な理解 - その4 (部分木dpの親側の穴埋め処理)
- 次は、部分木の木dpで埋まらなかった、dp[v][vの親]のdpを埋める説明をするよ。さっきと同じ図を再掲示します。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20240408/20240408105019.png)
- 色々と説明するより、コードを見て理解して欲しい。け、けっして手抜きなんかじゃないんだからねっ！
```swift
    func rec_p(_ v: Int, _ p: Int, _ pval: Int) {
        let gv = G[v]

        // dp[v][vの親]の穴埋め -- 処理①
        for i in 0..<gv.count {
            if gv[i] == p {
                dp[v][i] = pval
                continue
            }
        }

        // 子に渡す、cval(⇒dp[c][v])の作成前準備 -- 処理②
        var dpv_l = [Int](gv.count + 1,e)
        var dpv_r = [Int](gv.count + 1,e)
        for i in 0..<gv.count {
            dpv_l[i + 1] = mrg(dpv_l[i], dp[v][ i ]) // gvのインデックス昇順で累積
            dpv_r[i + 1] = mrg(dpv_r[i], dp[v][ gv.count-1 - i ]) // gvのインデックス降順で累積
        }

        // 子にcvalを渡す -- 処理③
        for i in 0..<gv.count {
            let c = gv[i]
            if c == p { continue }
            let dpv_exc_i = mrg(dpv_l[i], dpv_r[gv.count-1 - i])
            let cval = slfop(v,dpv_exc_i)
            rec_p(c, v, cval)
        }
    }
```
- お分かり頂けただろうか？
    - 補足すると、rec_pとしたのは、rec_cで埋めなかったdp[v][vの親]を埋めるから、parentのpです。
    - 当然ですが、先にrec_c(0,-1)を実行したなら、後から、rec_p(0,-1,?)を実行します。もし、rec_c(2,-1)としてたら、rec_p(2,-1,?)です。rec_pの3つ目の引数?は好きな数字を入れてください。pvalはdv[v][p]の穴埋めに使う数字ですが、根の親は存在しないので、?にどんな数字を入れても使われません。とは言え、何か入れないとエラーになるので、好きな数字でも入れておきましょう。好きな数字がなければ、eでも入れましょう。
- 一応、ポイントとしては、頂点vから子頂点cに渡すdp[c][v]の値cvalを作るときに高速化が必要だから、その処理をしています。
    - 上記コードでの、頂点vについての計算量を考えると...処理①、処理②、処理③それぞれで、O(gv.count)。
    - だから、全ての頂点での計算量合計は、Σgv.count{v in 0..<N} = 2×(N-1)より、O(N)になるね。$O(N^2)$じゃないよ。 
    - 処理②③での高速化を考えないと、下記の通りシンプルに書けますが、二重forループなので、$O((gv.count)^2)$となります。頂点vが極端なスターグラフの中心になってるときは、gv.count ≈ Nになるので、$O(N^2)$が発生してアウトだね。
```swift
        // 子にcvalを渡す -- 低速版
        for i in 0..<gv.count {
            let c = gv[i]
            if c == p { continue }
                //処理③からの変更箇所
                var dpv_exc_i = e
                for j in 0..<gv.count { // (ループ追加)
                    if j == i { continue }
                    dpv_exc_i = mrg(dpv_exc_i,dp[v][j])
                }
            let cval = slfop(v,dpv_exc_i)
            rec_p(c, v, cval)
        }
```
# 全方位木dpの理論的な理解 - その5 (各頂点vでの解答を得る)
- これは、特に説明しないよ。
```swift
    func answer(_ v: Int) -> Int {
        let gv = G[v]
        var ans = e
        for i in 0..<gv.count {
            ans = mrg(ans, dp[v][i])
        }
        return slfop(v, ans)
    }
```

# 全方位木dpを構造体とするコード
- コレまで説明した内容に基づき構造体を作りました。
- 構造体の名前は、[けんちょんさんの解説](https://drken1215.hatenablog.com/entry/2024/04/15/135700)と同様、「ReRooting」にしています。プロパティ名や関数名は好き勝手に変えちゃったけど。
```swift
extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

struct ReRooting {

    // モノイドさん達
    var e: Int // モノイドの単位元「e」:identity elementとか、unityとか。でも、uだとvと紛らわしいからeにするね。
    var mrg:(Int,Int)->Int // (dp,dp)→dp、モノイドの結合「･」
    var dp: [[Int]] // モノイドの集合「S」。dp[v][p]：頂点vを部分木の根とするが、vから伸びる辺の内、頂点pに伸びる辺を削除して考える。
    
    // モノイドを利用する人達
    var G:[[Int]] // グラフ：G[v]頂点vから伸びる辺の先の頂点が格納される。頂点0に頂点2,4,6が接続されていれば、G[0][0]=2,G[0][1]=4,G[0][2]=6
    var slfop:(Int,Int)->Int // (v,dp)→dp：頂点vでの自己処理。モノイドにおける写像とも言える？

    //イニシャライザ（ここで、dpを全部埋めちゃいます！)
    init(_ graph:[[Int]], _ unity: Int, _ merge: @escaping (Int,Int)->Int, _ selfoperation: @escaping (Int,Int)->Int) {
        G = graph
        e = unity
        mrg = merge
        slfop = selfoperation
        dp = [[Int]](G.count,[])

        // 最初に頂点0を根とする部分木dpを実行。このとき、dv[v][c]が埋まる。データ吸い上げ構造。
        rec_c(0, -1) // 根は頂点0じゃなくても良い、例えば、頂点(N-1)でもok。でも、rec_pも同じにすること。
        
        // rec_cの実行で埋まっていないdp[v][p]を埋める。データ押しつけ構造。
        rec_p(0, -1, e) // eの代わりに好きな数字でもok
        
    }

    mutating func rec_c(_ v: Int, _ p: Int) -> Int {
        let gv = G[v]
        var ans = e
        dp[v] = [Int](gv.count,e)
        for i in 0..<gv.count {
            let c = G[v][i] // childのcにしました。
            if c == p { continue }
            dp[v][i] = rec_c(c, v) // データ吸い上げ構造
            ans = mrg(ans, dp[v][i])
        }
        return slfop(v, ans) // 頂点vにおける木dpの解を吐き出す
    }

    mutating func rec_p(_ v: Int, _ p: Int, _ pval: Int) {
        let gv = G[v]
        
        // dp[v][vの親]の穴埋め -- 処理①
        for i in 0..<gv.count {
            if gv[i] == p {
                dp[v][i] = pval // データ押しつけ構造
                continue
            }
        }

        // 子に渡す、cval(⇒dp[c][v])の作成前準備 -- 処理②
        var dpv_l = [Int](gv.count + 1,e)
        var dpv_r = [Int](gv.count + 1,e)
        for i in 0..<gv.count {
            dpv_l[i + 1] = mrg(dpv_l[i], dp[v][ i ]) // gvのインデックス昇順で累積
            dpv_r[i + 1] = mrg(dpv_r[i], dp[v][ gv.count-1 - i ]) // gvのインデックス降順で累積
        }

        // 子にcvalを渡す -- 処理③
        for i in 0..<gv.count {
            let c = gv[i]
            if c == p { continue }
            let dpv_exc_i = mrg(dpv_l[i], dpv_r[gv.count-1 - i])
            let cval = slfop(v,dpv_exc_i)
            rec_p(c, v, cval) // データ押しつけ構造
        }
        
        // 子にcvalを渡す -- 低速版
        // for i in 0..<gv.count {
        //     let c = gv[i]
        //     if c == p { continue }
        //         //処理③からの変更箇所
        //         var dpv_exc_i = e
        //         for j in 0..<gv.count { // (ループ追加)
        //             if j == i { continue }
        //             dpv_exc_i = mrg(dpv_exc_i,dp[v][j])
        //         }
        //     let cval = slfop(v,dpv_exc_i)
        //     rec_p(c, v, cval) // データ押しつけ構造
        // }
        
    }

    func answer(_ v: Int) -> Int {
        let gv = G[v]
        var ans = e
        for i in 0..<gv.count {
            ans = mrg(ans, dp[v][i])
        }
        return slfop(v, ans)
    }
}
```
- さっきの説明で省略してたけど、プロパティを変更する関数は、頭に`mutating`を付けてます。

# 今回の問題
- やっと、 [コイツ](https://atcoder.jp/contests/dp/tasks/dp_v)を倒すことが出来ます。
- コイツを倒すコードはコレだ！
```swift
//グラフセット（無指向辺）頂点番号1減済み
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var gs = [[Int]](repeating:[],count:N)
for _ in 0..<N-1 {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    gs[a] += [b]
    gs[b] += [a]
}

// 全方向木dpのインスタンス生成
var rr = ReRooting(
            gs, // グラフ
            1, // unity
            { a, b in (a * b) % M }, // merge
            { _, a in (a + 1) % M } // selfoperation
        )

// 解答を出力
for v in 0..<N {
    print((rr.answer(v) + M - 1) % M)
}
```
- 特に説明は要らないかな？
- ただ、最初の考え方と変えた部分があるから補足するよ。
    - 最初に「TLE覚悟で、普通の木dpで解いてみる」で書いたコードのdpは、頂点vが黒になるときの場合の数にしてたよ。まあ、題意通りの設定だね。
    - でも、その場合、子vから親nodeにdpを渡すときの計算は、`dp[node] *= (dp[v] + 1)`のように、頂点vが白になる場合の数1を加える必要があった。
    - 今回は、白になる場合の数1を予めdpに足している(selfoperation)
    - もし、予め1を足していないと、上記のmerge,selfoperationは、このように書く事になるだろうか？
```swift
            { a, b in ((a+1) * (b+1)) % M }, // merge
            { _, a in (a) % M } // selfoperation
```
- もちろん、上記は駄目だよ。mergeはモノイドに対して行うものだから、足し算と、掛け算が混ざってるのは駄目!
    - 上記みたいな木で鼻を括ったような説明はよくないね。木dpだけに...
    - もう少し補足すると、今回モノイドを導入するにあたり、eという単位元を設定したよね。そして、merge(e,e)=eを満たさないといけない。
    - でも、`{ a, b in ((a+1) * (b+1)) % M }`は明らかにmerge(e,e)=eを満たしていないよね。だから駄目なんです。
    - merge(e,e)=eを満たすように設定したmerge関数が、`{ a, b in (a * b) % M }`になったと言うことです。

# おわりに
- 今回は、久しぶりの大作となりました。3連休を潰して、それでも足りなかったよ。
- 時間をかけたから、全方位木dpの解説としては、かなり詳細なものができたと思う。勿論、けんちょんさんの解説のお陰だけど、けんちょんさんの解説を読み解けなかった人には役立てるかな？
- ところで、今回はReRooting構造体を作ったから、今後、全方位木dpがコンテストに出たら、速攻で解けるぜ！やったぜ！
- まぁ、よい週末だったよ。三連休中に買ったipadの使い道も見つけられたしね。