質問する

Access

質問へのアクセス

これは、ツリーを両側に引っ張って直径(最長パス)を求める問題です.これは,リーフノード間の最長距離を求めるとすぐに説明できる.

Algorithm

概要

しかし,リーフノードを先に求め,次にBrout Forsとして距離を一つ一つ求めると,時間的制約を受けることは間違いない.したがって、ツリー内で遍歴すると、逆トラッキングを使用して幹線値を蓄積する方法が使用されます.
各頂点にはリーフノードの直径値が格納され、各幹線にはリーフノードからの累計幹線値が格納されます.

オーダー

次のように木があるとします.

各頂点の値を-1に設定します.リーフノード間でコストが見つからないためです.

下部リーフノードを移動します.

リーフノードの直径は0です.サブノードが存在しないためです.したがって、各リーフノードの頂点値はゼロになります.

リーフノードの整理が完了しましたので、上へ移動し続けてください.このノードは、2つのリーフノードから直径を作成できます.したがって,ノードの直径値は7+1=8である.

先ほどの2つのリーフノードのうち、左側の幹線値(7)はもっと大きいです.したがって、親ノードの幹線値には、以前の幹線値が累積されます.
他のサブノードの進行状況は同じです.


これでルートノードの前のノードの計算が完了します.最後に、ルートノードの点の直径を求めることができます.これは、既存のノードと同じです.ここで、直径の値は17であり、3本の幹線(11、6、5)のうち11、6が順に大きいためである.

だから使うアルゴリズムは?

ツリーを最下層に移動し、上に向かって計算するため、DFSとbacktrackingを使用します.また、累積した幹線値を追加または保存する必要があるため、ダイナミックプログラミングも使用されます.

Code

初期化

tree = collections.defaultdict(list)
vals = collections.defaultdict(tuple)

tree:ツリーを表します.keyは親ノードとなり、valueは子ノードのリストです.

vals:保存する頂点と幹線の値を累計します.keyは頂点名、valueは(幹線値、その位置が最も長いリーフノード間の距離)です.

入力

for _ in range(N-1):
    start, end, value = list(map(int, input()[:-1].split()))
    tree[start].append(end)
    vals[end] = (value, -1)
vals[1] = (0, -1)

valsは、親ノードではなくサブノードをキーとして使用し、値を保存します.これは、子ノードからの幹線値が格納されているため、親ノードの位置の幹線値を比較できます.
ただし、ルートノードの値は、サブノードがkeyであるため初期化されていません.したがって、(0,-1)として保存されます.ルートから延びる幹線がないので0に設定します.

プログラム

これらの値が初期化されている場合は、ノード番号1から開始し、再帰を続行します.
パラメータは頂点kを受信し、戻り値はvals配列に蓄積された幹線値と直径を格納する必要はない.

def __search(k: int):
    # k: key

    # if leafnode
    if k not in tree:
        # 지름 값 없음
        vals[k] = (vals[k][0], 0)
    else:
        # 아닌 경우
        candidate_edges = []

        for child_k in tree[k]:
            # child edge 순회
            __search(child_k)
            # 후보 Edge값 push
            heapq.heappush(candidate_edges, -vals[child_k][0])

        # child edge가 하나인 경우
        # 해당 key에서 지름 못구함 따라서 지름은 추가 하지 않고 누적 edge 값만
        if len(candidate_edges) == 1:
            vals[k] = (vals[k][0] + -(heapq.heappop(candidate_edges)), 0)
        else:
            # 두개 이상이면 가장 값이 큰 두개 사용
            fst_e = -heapq.heappop(candidate_edges)
            snd_e = -heapq.heappop(candidate_edges)
            vals[k] = (vals[k][0] + fst_e, fst_e + snd_e)
        # 간선 값 리턴
        return vals[k][0]

リーフノードの場合

以下に比較可能な幹線値がないためvalsに幹線値と0を格納する.

vals[k] = (vals[k][0], 0)

ブランチノードの場合

サブノードを巡回して、累積した幹線値を計算します.復元が終了すると、リーフノードから頂点までの最大幹線値の計算が完了します.したがって、サブノードの累積幹線値をheapにロードして保存します.Heapに保存するのは、ソートアルゴリズムのコストを削減するためです.後で2つの最大幹線値を指定する必要があるからです.
サブノードを巡回すると、プロセスは1つのサブノードと2つのサブノードに分けられます.

candidate_edges = []

for child_k in tree[k]:
    # child edge 순회
    __search(child_k)
    # 후보 Edge값 push
    heapq.heappush(candidate_edges, -vals[child_k][0])

サブノードが1つしかない場合。

比較可能な内容がないため、他のプロセスがない場合、サブノードの幹線値を累積してノードの既存の幹線値に格納する.また、サブノードが1つしかないノードは直径にできないので、0に保存します.

vals[k] = (vals[k][0] + -(heapq.heappop(candidate_edges)), 0)

2つ以上

2つ以上の値がある場合は、2つの最大の幹線値を入力します.次に、最大の1つの幹線値をノードの値に蓄積し、2つ以上のサブノードを有するノードが直径を有することができるため、2つの幹線値の合計を直径として記憶する.

fst_e = -heapq.heappop(candidate_edges)
snd_e = -heapq.heappop(candidate_edges)
vals[k] = (vals[k][0] + fst_e, fst_e + snd_e)

例外処理

しかし、このような形の木も存在する.

既存のシェイプのツリーとは異なり、サブノードが1つしかないルートノードは、独自のリーフノードであってもよい.したがって、valsのルートノード(1)セクションで次の変更を行います.ルートノードにサブノードが1つしかない場合、幹線値は直径になります.

if len(tree[1]) == 1:
    vals[1] = (vals[1][0], vals[1][0])

最大直径を求める

valsのvalue部分をリストに個別に収集し、最大直径値の順に並べ替えます.

r = list(vals.values())
r.sort(key=lambda x: x[1], reverse=True)
answer = r[0][1]
print(answer)