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

Last updated at 2024-11-07Posted at 2024-11-05

はじめに

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

対戦相手

コイツです。
まず、頂点数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で解いてみる

倒れるときは、前のめり!...と言うことで、駄目と分かっていても解くね。

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の手法でイケたね。
あぁ、提出結果はもちろんTLEです。

無駄にあがいてみた

メモ化でdp計算結果を使い回すことで計算量削減できないかな？と思ってあがいたのが次のコード

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が出るケースについて分析している方がいました。一つの頂点に多数の辺が接続しているとき（スターグラフと呼ぶ）でアウトみたいです。なるほど、勉強になります！

全方位木dpとは？

「全方位木」を使ったdpではなく、全方位の「木dp」って意味みたい。
で、いろいろな人達の解説を見て、概ね理解したよ。
まず、手順について結論から言います。考えるんじゃない、感じるんだ！
- ①最初に、適当な頂点vを決めて、木dpをして、頂点vの答えを出します。コレは再帰関数を使うから、実体は深さ優先探索だね。
  - 計算量がシビアじゃなければ、vは頂点1(0-idxなら、頂点0)の決め打ちで良いね。
- ②次に、頂点vから、幅優先探索で、各頂点の答えを出していきます。
図で書いた方が分かり易いね。昨日、ipad miniとapple pencilを買ったから、活用しちゃうよ！
最初は頂点vを根とした木dpを行います。この時の情報の流れを赤矢印で示します。
この時、頂点vは解答の情報を持っているのは、ご承知のとおりです。
次に、頂点vから情報を下ろしていきます。下ろしていく矢印を紫色にしています。これは、幅優先探索で下ろします。
頂点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)については、昔やったコレで復習します。

上記方針に基づいて全方位木dpをコードにする

駄目でした！
なんの成果も!! 得られませんでした!!（号泣）
前項でぇ、偉そうにぃ、ans[1] = dp[1] * (ans[0] / (dp[1] + 1) + 1) -- これもまぁ、分かるよね。dpの時と似てるよね。とか書いてるじゃないですかぁ。
コレ駄目ですわ。 dpやansがmod計算されてんのに割り算とかしちゃアカンですわ 。詳しくはコチラ。
じゃあ、どうやって、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のアルゴリズムを僕なりに噛み砕いて解説します。

まず、全方位木dpの話に入る前に、部分木に関する木dpの話をします。
例えば、上図例で頂点2を根として、頂点5の部分木dpを考えます。
dpは以下のとおり考える。
頂点vに対し、初期値e(加算計算なら0，乗算計算なら1),頂点vの子cldrn[0],cldrn[1],...がいる前提として、下記のコードが成立するものと考えます。v=5なら、cldrn = [7,9]になるよね。

dp[v] = e // mergeが加算計算なら0、乗算計算なら1
for cld in cldrn {
    dp[v] = merge(dp[v],dp[cld])
}
dp[v] = sefloperation(v,dp[v])

上記のmergeは別途設定する関数になります。
- ちょっと数学的な話をしちゃうね。
- モノイドの組 (S, •, e)と上記dp計算の対比をするね。
- 「S」は配列dp、「･」は関数merge、「e」はe（eは単位元と呼ぶ）となります。
続いて、selfoperationってなんじゃい！って感じだよね。、cldの情報だけでなく、cld以外の情報（通常、自ノードに紐付いた情報）も使って答えを出すのに必要な関数です。この作業を行う関数をselfoperationと名付けました。
- あれ？mergeがモノイドの結合「・」だったけど、selfoperationって、モノイドの何？って思った人いるよね？
  - ...細けぇ事はいいんだよ！適当なこと言えば、写像とでも思っておけばいいんじゃね？（なげやり）
ここまでは、学習済みの部分木に関する木dpをモノイドの概念を使って解く場合の整理です。
実はここまで、全方位木dpの説明は全くしてません(キリッ)

全方位木dpの理論的な理解 - その2 (dpの2次元化)

で、ここから全方位木dpの説明を始めるよ。さっきと同じ図を再掲示します。
ポイント！
- 普通の木dpでは木全体の根は固定でした。そして、例えば、根を頂点2と考えたとき、頂点5の部分木dpとして存在するのはdp[5]一つだけでした。
- しかし、全方位木dpでは根が固定されないため、dp[5]を一つの値としてしまうと、頂点9を根とした場合の部分木としてのdpに使えません。よって、dp[5]をたった一つの値にすることを諦めます。
- 答えを先に書いちゃうと2次元化します。
さて、基本に立ち返って、dp[5]はどうやって算出したでしょうか？

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の説明をするよ。さっきと同じ図を再掲示します。
dpを二次元化したら、再帰関数rec_cは以下のように書きます。
- ちなみに、この段階では部分木dpだから、仮に木全体の根を頂点0とした場合、dp[5][頂点2]は計算されず、dp[5][頂点7]とdp[5][頂点9]だけ計算されます。

    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を埋める説明をするよ。さっきと同じ図を再掲示します。
色々と説明するより、コードを見て理解して欲しい。け、けっして手抜きなんかじゃないんだからねっ！

    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)$が発生してアウトだね。

        // 子に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での解答を得る)

これは、特に説明しないよ。

    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を構造体とするコード

コレまで説明した内容に基づき構造体を作りました。
構造体の名前は、けんちょんさんの解説と同様、「ReRooting」にしています。プロパティ名や関数名は好き勝手に変えちゃったけど。

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を付けてます。

今回の問題

やっと、コイツを倒すことが出来ます。
コイツを倒すコードはコレだ！

//グラフセット（無指向辺）頂点番号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は、このように書く事になるだろうか？

            { 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の使い道も見つけられたしね。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up