概要

この問題は、グラフから辺を1本取り除いた後の最小全域木（MST）の重みの最大値を求める問題です。

青木君は高橋君が作るMSTの総コストを最大化しようとしますが、MSTに含まれない辺を削除してもMSTの重みは変わりません。そのため、青木君は「もともとのMSTに含まれる辺」のうち、それを削除した際に代わりとなる辺（代替辺）のコストが最も大きくなるような辺を1本選んで切断することになります。

考察

1. どの辺を切断すべきか？

まず、グラフ全体の最小全域木 \(T\) を求めます。 - 青木君が \(T\) に含まれない辺を切断した場合：高橋君は依然として \(T\) を構築できるため、MSTの重みは変わりません。 - 青木君が \(T\) に含まれる辺 \(e\) を切断した場合：高橋君は \(e\) の代わりに、\(T \setminus \{e\}\) を再び連結にするような辺 \(e'\) のうち、最もコストが小さいものを選んで新しいMSTを構築します。

したがって、青木君の戦略は 「MSTに含まれる各辺 \(e\) について、それを切断した後の最小コスト増加量を計算し、その増加量が最大になる \(e\) を選ぶ」 ことになります。

2. 代替辺の条件

MST \(T\) に含まれる辺 \(e\) を切断すると、木 \(T\) は2つのコンポーネントに分かれます。これらを再び繋ぐことができる辺 \(e' = (u, v)\) は、「もともとの木 \(T\) において、頂点 \(u, v\) を結ぶパス上に辺 \(e\) が含まれている」 ような辺です。

高橋君は、このような \(e'\) の中で重み \(W_{e'}\) が最小のものを選びます。

3. 効率的な計算方法

愚直にすべての辺 \(e \in T\) に対して代替辺を探すと、最悪 \(O(NM)\) かかり間に合いません。そこで、以下の性質を利用します。

• すべての非MST辺 \((u, v, w)\) について考える。この辺は、木 \(T\) 上の \(u\) から \(v\) へのパスに含まれるすべての辺 \(e\) に対して、重み \(w\) の「代替辺候補」となる。
• 各辺 \(e \in T\) について、自分をパスに含む非MST辺の中で最小の重み \(w\) を知りたい。

これは、「非MST辺を重みの昇順にソートし、まだ代替辺が決まっていない木上のパスを塗りつぶしていく」 という操作で解くことができます。

アルゴリズム

1. 最小全域木 (MST) の構築: クラスカル法を用いてMSTを求め、その総重みを \(S\) とします。MSTに含まれる辺の集合を \(E_{MST}\)、含まれない辺の集合を \(E_{other}\) とします。
2. 木構造の整理: MSTを根付き木として扱い、各頂点の深さと親への辺を記録します。また、ダブリング（Binary Lifting）を用いて、最小共通祖先 (LCA) を高速に求められるようにします。
3. 代替辺の決定 (パス被覆): \(E_{other}\) の辺を重み \(W\) の昇順にソートします。各辺 \((u, v, w) \in E_{other}\) について、\(u\) から \(v\) へのパス上にある辺のうち、まだ代替辺が割り当てられていない辺すべてに重み \(w\) を割り当てます。
   • この「未割り当ての辺を飛ばす」操作を高速化するため、Union-Find (DSU) を活用します。各頂点について「その頂点より上方向で、まだ未処理の辺がある最も近い頂点」を DSU で管理することで、各辺を一度だけ走査する \(O(M \alpha(N))\) の計算量で処理できます。
4. 答えの計算: 各辺 \(e \in E_{MST}\) について、その代替辺の重みを \(W_{alt}(e)\) とすると、その辺を切断した後のMSTの重みは \(S - W_e + W_{alt}(e)\) です。 これらと元の \(S\) の中での最大値が答えとなります。

計算量

• MSTの構築: \(O(M \log M)\) または \(O(M \log N)\)
• LCAの構築: \(O(N \log N)\)
• 代替辺の計算 (ソート + DSUパス被覆): \(O(M \log M + M \alpha(N))\)
• 時間計算量: \(O(M \log M)\)
• 空間計算量: \(O(N \log N + M)\)

実装のポイント

• 再帰制限: Pythonの場合、深い木の走査で再帰回数制限に達しやすいため、DFSや木の構築はスタックを用いた反復形式（Iterative）で実装するのが安全です。

• DSUによるパス短縮: パスを遡る際、一度処理した頂点は dsu.union(current, parent) のようにして飛ばすことで、計算量を劇的に落とすことができます。

• 2-辺連結性の保証: 問題文でグラフが 2-辺連結であることが保証されているため、すべての \(e \in E_{MST}\) に対して必ず代替辺が存在します。

  ソースコード

import sys

# Increase recursion depth for safety, though iterative methods are used
sys.setrecursionlimit(300000)

def solve():
    # Efficiently read input data
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    
    edges = []
    for i in range(M):
        u = int(next(it))
        v = int(next(it))
        w = int(next(it))
        edges.append((u, v, w, i))
    
    # Kruskal's algorithm to find the Minimum Spanning Tree (MST)
    # Sort edges by weight to build MST
    edges.sort(key=lambda x: x[2])
    parent_mst = list(range(N + 1))
    
    # Iterative DSU find function
    def find(p, i):
        root = i
        while p[root] != root:
            root = p[root]
        while p[i] != root:
            nxt = p[i]
            p[i] = root
            i = nxt
        return root

    mst_weight = 0
    mst_edge_indices = []
    non_mst_edges = []
    adj = [[] for _ in range(N + 1)]
    edge_weights = [0] * M
    
    for u, v, w, i in edges:
        edge_weights[i] = w
        root_u = find(parent_mst, u)
        root_v = find(parent_mst, v)
        if root_u != root_v:
            parent_mst[root_u] = root_v
            mst_weight += w
            mst_edge_indices.append(i)
            adj[u].append((v, i))
            adj[v].append((u, i))
        else:
            # Non-MST edges are candidates for replacing removed MST edges
            non_mst_edges.append((u, v, w, i))
    
    # Root the MST at node 1 and precompute depths and parents using iterative DFS
    depth = [0] * (N + 1)
    parent_node = [0] * (N + 1)
    edge_to_parent_idx = [-1] * (N + 1)
    stack = [1]
    visited = [False] * (N + 1)
    visited[1] = True
    while stack:
        u = stack.pop()
        for v, i in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent_node[v] = u
                edge_to_parent_idx[v] = i
                depth[v] = depth[u] + 1
                stack.append(v)
    
    # Precompute binary lifting table for Lowest Common Ancestor (LCA)
    LOGN = (N).bit_length()
    up = [[0] * (N + 1) for _ in range(LOGN)]
    up[0] = parent_node
    for i in range(1, LOGN):
        up_prev = up[i-1]
        up_curr = up[i]
        for u in range(1, N + 1):
            up_curr[u] = up_prev[up_prev[u]]
    
    def get_lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for i in range(LOGN):
            if (diff >> i) & 1:
                u = up[i][u]
        if u == v:
            return u
        for i in range(LOGN - 1, -1, -1):
            up_i = up[i]
            if up_i[u] != up_i[v]:
                u = up_i[u]
                v = up_i[v]
        return up[0][u]
    
    # DSU for path covering to efficiently find the minimum replacement weight for each MST edge
    # dsu_path[i] points to the highest ancestor of node i whose parent-edge hasn't been processed
    dsu_path = list(range(N + 1))
    replacement_weight = [-1] * M
    
    # Process non-MST edges (already sorted by weight) to cover edges on the tree paths
    for u, v, w, i in non_mst_edges:
        lca = get_lca(u, v)
        # Traverse path from u to lca
        curr = find(dsu_path, u)
        while depth[curr] > depth[lca]:
            idx = edge_to_parent_idx[curr]
            if replacement_weight[idx] == -1:
                replacement_weight[idx] = w
            # Use DSU to jump over this edge in future traversals
            dsu_path[curr] = find(dsu_path, parent_node[curr])
            curr = dsu_path[curr]
        # Traverse path from v to lca
        curr = find(dsu_path, v)
        while depth[curr] > depth[lca]:
            idx = edge_to_parent_idx[curr]
            if replacement_weight[idx] == -1:
                replacement_weight[idx] = w
            dsu_path[curr] = find(dsu_path, parent_node[curr])
            curr = dsu_path[curr]
    
    # Aoki wants to maximize the weight of the resulting MST after removing one edge
    # If he removes an edge not in the MST, the MST weight remains mst_weight
    # If he removes an MST edge e, the weight becomes mst_weight - W(e) + W(replacement_e)
    ans = mst_weight
    for i in mst_edge_indices:
        if replacement_weight[i] != -1:
            ans = max(ans, mst_weight - edge_weights[i] + replacement_weight[i])
    
    # Output the maximized MST weight
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。