[BOJ 13325, Python] 二分木

問題リンク

[BOJ 13325](https://www.acmicpc.net/problem/13325

)

カテゴリ

動的計画法、木、木における動的計画法

説明

私のような場合は、すぐに解けない問題であっても、かなり長い間寝かせてじっくり考えるタイプだ！

そうしているうちに、このように試してみたが正解しなかった問題や、コンテストの問題と共に大掛かりな試みをしたものの解けなかった問題が溜まっていくことになる。

これらを片付けるために、たまに問題を読み返しながらじっくり考えるのだが、今日ついにこの記事で問題の解決法を知ることができてとても嬉しい！

なんと最初の試みから8ヶ月もかかった問題で、直前の試みから何度か手を出してみたことはあったが、適切な案が浮かばず解決できなかった。

def pre_order_detail(graph_dict: dict, target_node: int = 1) -> list:

    result = [target_node]

    if len(graph_dict[target_node]) >= 1:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][0]):
            result.append(each_element)
        result.append(target_node)

    if len(graph_dict[target_node]) >= 2:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][1]):
            result.append(each_element)
        result.append(target_node)

    return result

本来は、上記のような再帰関数の形で前走順回を変形させた形で、訪問するノードを出力した後、スタックのようなデータ構造に入れて各辺をあれこれ処理する方式を考えていた。

しかし、考えてみると、結果的に比較対象を同じ親ノードから出る辺に限定すれば、2つずつ比較した値のうち大きい方を着実に上位の辺に合算しながら処理する場合、きれいに計算できることが分かった！

後で解いて分類を見てみると、この種の問題はツリーDPと呼ばれるらしい。確かにDPのそれとは非常に似ていると実感した。

解答コード

# 이진 트리

import sys

input = sys.stdin.readline

tree_height = int(input())
node_number = pow(2, tree_height + 1)

edges = [0] + list(map(int, input().split()))
edge_sum = sum(edges)

now_start = node_number // 2 - 1
now_end = node_number - 1

while now_end:

    for i in range((now_end - now_start) // 2):

        child_edge = now_start + (2 * i)
        next_node = child_edge // 2

        edges[next_node] += max(edges[child_edge], edges[child_edge + 1])
        edge_sum += abs(edges[child_edge] - edges[child_edge + 1])

    now_end = now_start
    now_start = now_start // 2

print(edge_sum)

最初に考えていた方式よりも、コードの長さも時間計算量もすっきりした形になった。こうして見ると、確かにボトムアップ（Bottom-Up）の形式をとっている。