概要

青木君が「1 本の辺を切る」→高橋君が「残りで最小全域木 (MST) を作る」という順番のゲームで、最終的な MST コストを最大化する切断辺を考えます。結論として「MST の辺を 1 本切ったときの最小の代替辺」を全ての MST 辺について求め、その結果の最大値を出します。

考察

1. どの辺を切ると MST のコストが増えるか

まず元のグラフで MST を 1 つ作り、その重み和を \(T\) とします。

• MST に含まれない辺を 1 本切っても、同じ MST がそのまま残るので MST コストは \(T\) のままです（減ることも増えることもありません）。
• MST に含まれる辺 \(e\) を切ると、MST は 2 つの連結成分に分かれます。再び木に戻すには、その 2 成分を結ぶ別の辺（代替辺）を 1 本入れる必要があります。
  このとき新しい MST コストは [ T - w(e) + \min(\text{切断で分かれた 2 成分を結ぶ辺の重み}) ] となります。

よって青木君の狙いは、「MST の各辺を切ったときの上式」を計算して、その最大値を取ることです。

2. 素朴解が間に合わない理由

各 MST 辺 \(e\) を 1 本ずつ削除して MST を作り直すと、1 回 \(O(M \log N)\) かかり、これを \(N\) 回やるので \(O(NM \log N)\) になってしまい、\(N=10^5, M=2\times 10^5\) では到底無理です。

3. 解決の核心：「代替辺の最小値」を全辺まとめて求める

MST の辺 \(e\) を切ったときの代替辺の最小重みは、次の見方ができます。

• MST に含まれない辺 \((u,v)\) を 1 本足すと、MST 上で \(u\) と \(v\) を結ぶ道と合わせて ちょうど 1 つのサイクルができます。
• このサイクル上の MST 辺は「その非木辺で置き換え可能」です。
• したがって、ある MST 辺 \(e\) の代替辺の最小重みは
  「\(e\) を含むサイクルを作れる非木辺の重みの最小」
  ＝「MST 上の該当パスをまたぐ非木辺の重みの最小」です。

これを全 MST 辺について高速に求めます。

アルゴリズム

手順 1: Kruskal で MST を 1 つ作る

• 辺を重み昇順に見て Union-Find で採用し、MST を構成。
• MST の総和 \(T\) を得る。
• MST の隣接リストも作っておく（後で木として扱う）。

手順 2: 木 (MST) 上のパスを高速に区間へ分解する（HLD）

MST 上の「頂点 \(u\) から \(v\) のパス上にある辺全部」に同じ値を適用したい場面が出ます。そこで Heavy-Light Decomposition (HLD) を使い、木上のパスを \(O(\log N)\) 個の連続区間（配列上の区間）に分解できるようにします。

実装上の対応： - 各頂点 \(v (\neq \text{root})\) に対し、親への辺の重み pw[v] を持つ。 - HLD の pos[v] により、「親への辺」を配列の 1 要素として扱う。
具体的には 辺 (parent[v], v) を pos[v] に対応させます（root は例外）。

手順 3: 非木辺を重み昇順に処理し、パス上の「未確定の辺」に最小代替重みを入れる

やりたいことは： - MST の各辺 \(e\) について「代替辺の最小重み」repl[e] を求める。

そこで、 1. 非木辺 \((u,v,w)\) を 重み昇順に並べる。 2. その非木辺が作るサイクル＝MST 上のパス \(u \to v\) に含まれる各 MST 辺は、代替候補として重み \(w\) を持つ。 3. ただし「最小」が欲しいので、まだ repl が決まっていない辺にだけ \(w\) を入れたい。

ここで重要テクニックとして、配列区間に対して - 「まだ未確定の位置だけを次々埋める」 ことを高速にするため、nxt という “次の未確定位置” を指す Union-Find もどきを使います。

• paint(l, r, w)：区間 \([l,r]\) のうち未確定な位置だけに repl= w を入れ、埋めた位置は nxt でスキップできるようにする。
• 非木辺を重み昇順で処理しているので、最初に埋まった値がその辺の 最小代替重みになります。

HLD によりパスは複数区間になるので、各区間に paint を呼びます。

手順 4: 「MST 辺を切ったときの MST コスト」を全て計算して最大を取る

MST の各辺 (parent[v], v)（root 以外の各頂点 v に対応）について、 - その辺の重みは pw[v] - 代替辺の最小重みは repl[pos[v]]

よって切断後の最小全域木コストは [ T - pw[v] + repl[pos[v]] ] これを全 \(v=1..N-1\) で最大化し、また「非 MST 辺を切る」場合の \(T\) も候補なので、最終答えはその最大値です。

なお問題の条件「2-辺連結」より、どの MST 辺を切っても必ず代替辺が存在し、repl は必ず有限になります。

計算量

• 時間計算量:
  
  • Kruskal: \(O(M \log M)\)
    
  • HLD 構築: \(O(N)\)
    
  • 非木辺処理: パス分解が \(O(\log N)\) 個の区間、ただし paint は各位置を高々 1 回だけ埋めるので全体で \(O((N + M)\alpha(N) + M \log N)\) 程度
    よって全体として概ね
    [ O(M \log M + M \log N) ]
• 空間計算量: \(O(N + M)\)

実装のポイント

• 辺→配列位置の対応：pos[v] は「頂点 v そのもの」ではなく 親への辺を表す（root は対応する辺がないので例外扱い）。

• パス更新で LCA の辺を含めない：同一 heavy-path 内の最後は l = pos[v] + 1 として、LCA 側の「親への辺」を誤って含めないようにしています。

• nxt によるスキップ：paint は「未確定な場所だけ埋める」ための典型テクで、区間を愚直に塗ると \(O(NM)\) になり得るのを防ぎます。

• root の扱い：repl[pos[root]] は使わないので、最初から埋めた扱いにしてスキップしています。

  ソースコード

import sys


class DSU:
    __slots__ = ("p", "sz")

    def __init__(self, n: int):
        self.p = list(range(n))
        self.sz = [1] * n

    def find(self, x: int) -> int:
        p = self.p
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        p = self.p
        sz = self.sz
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if sz[a] < sz[b]:
            a, b = b, a
        p[b] = a
        sz[a] += sz[b]
        return True


def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    U = [0] * M
    V = [0] * M
    W = [0] * M
    for i in range(M):
        U[i] = next(it) - 1
        V[i] = next(it) - 1
        W[i] = next(it)

    # Kruskal to build one MST
    dsu = DSU(N)
    order = sorted(range(M), key=W.__getitem__)
    in_mst = [False] * M
    mst_adj = [[] for _ in range(N)]
    total = 0
    taken = 0
    for ei in order:
        if dsu.union(U[ei], V[ei]):
            in_mst[ei] = True
            w = W[ei]
            u = U[ei]
            v = V[ei]
            mst_adj[u].append((v, w))
            mst_adj[v].append((u, w))
            total += w
            taken += 1
            if taken == N - 1:
                break

    # HLD preprocessing on MST (root = 0)
    parent = [-1] * N
    depth = [0] * N
    pw = [0] * N  # weight to parent
    st = [0]
    dfs_order = []
    while st:
        v = st.pop()
        dfs_order.append(v)
        for to, wt in mst_adj[v]:
            if to == parent[v]:
                continue
            parent[to] = v
            depth[to] = depth[v] + 1
            pw[to] = wt
            st.append(to)

    children = [[] for _ in range(N)]
    for v in range(1, N):
        children[parent[v]].append(v)

    size = [0] * N
    heavy = [-1] * N
    for v in reversed(dfs_order):
        s = 1
        best = 0
        hv = -1
        for c in children[v]:
            sc = size[c]
            s += sc
            if sc > best:
                best = sc
                hv = c
        size[v] = s
        heavy[v] = hv

    head = [0] * N
    pos = [0] * N
    cur = 0
    stack = [(0, 0)]
    while stack:
        v, h = stack.pop()
        while True:
            head[v] = h
            pos[v] = cur
            cur += 1
            hv = heavy[v]
            for c in children[v]:
                if c != hv:
                    stack.append((c, c))
            if hv != -1:
                v = hv
            else:
                break

    # Offline compute min replacement edge for each tree edge by processing non-tree edges in increasing weight.
    non_tree = [(W[i], U[i], V[i]) for i in range(M) if not in_mst[i]]
    non_tree.sort()

    INF = 10**30
    repl = [INF] * N  # by position; repl[pos[root]] is unused
    nxt = list(range(N + 1))  # DSU "next unassigned" over positions

    def uf_find(x: int, nxt=nxt) -> int:
        while nxt[x] != x:
            nxt[x] = nxt[nxt[x]]
            x = nxt[x]
        return x

    # mark root position as already assigned (skip)
    root_pos = pos[0]
    repl[root_pos] = 0
    nxt[root_pos] = uf_find(root_pos + 1)

    def paint(l: int, r: int, w: int, repl=repl, nxt=nxt, uf_find=uf_find) -> None:
        x = uf_find(l)
        while x <= r:
            repl[x] = w
            nxt[x] = uf_find(x + 1)
            x = nxt[x]

    def apply_path(u: int, v: int, w: int,
                   head=head, depth=depth, parent=parent, pos=pos, paint=paint) -> None:
        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]:
                u, v = v, u
            paint(pos[head[u]], pos[u], w)
            u = parent[head[u]]
        if depth[u] < depth[v]:
            u, v = v, u
        l = pos[v] + 1
        r = pos[u]
        if l <= r:
            paint(l, r, w)

    for w, u, v in non_tree:
        if uf_find(0) == N:
            break
        apply_path(u, v, w)

    # Compute worst-case MST weight after removing one edge
    ans = total
    for v in range(1, N):
        rw = repl[pos[v]]
        # rw should be finite due to 2-edge-connectedness
        cand = total - pw[v] + rw
        if cand > ans:
            ans = cand

    sys.stdout.write(str(ans))


if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。