Overview

This is a game where Aoki “cuts one edge” → then Takahashi “builds a minimum spanning tree (MST) from the remaining edges.” We need to find the cut edge that maximizes the final MST cost. The conclusion is: for every MST edge, find the minimum-weight replacement edge when that edge is cut, then output the maximum result among all of them.

Analysis

1. Which edge, when cut, increases the MST cost?

First, build one MST of the original graph and let its total weight be \(T\).

• If we cut an edge not in the MST, the same MST remains intact, so the MST cost stays at \(T\) (it neither increases nor decreases).
• If we cut an edge \(e\) in the MST, the MST splits into two connected components. To form a tree again, we need to add one alternative edge (replacement edge) connecting the two components.
  The new MST cost becomes: [ T - w(e) + \min(\text{weight of edges connecting the two components after the cut}) ]

Therefore, Aoki’s strategy is to compute the above expression for each MST edge and take the maximum.

2. Why a naive solution is too slow

If we delete each MST edge \(e\) one at a time and rebuild the MST, each rebuild costs \(O(M \log N)\), and doing this \(N\) times gives \(O(NM \log N)\), which is far too slow for \(N=10^5, M=2\times 10^5\).

3. The key insight: computing the “minimum replacement edge” for all edges at once

The minimum replacement weight when MST edge \(e\) is cut can be viewed as follows:

• Adding a non-tree edge \((u,v)\) to the MST creates exactly one cycle together with the path from \(u\) to \(v\) on the MST.
• The MST edges on this cycle can be “replaced by that non-tree edge.”
• Therefore, the minimum replacement weight for an MST edge \(e\) is
  “the minimum weight among non-tree edges that form a cycle containing \(e\)”
  = “the minimum weight among non-tree edges that span the corresponding path on the MST.”

We compute this efficiently for all MST edges.

Algorithm

Step 1: Build one MST using Kruskal’s algorithm

• Sort edges by weight in ascending order and use Union-Find to select edges, constructing the MST.
• Obtain the MST total weight \(T\).
• Also build the adjacency list of the MST (to treat it as a tree later).

Step 2: Decompose paths on the tree (MST) into intervals efficiently (HLD)

We need to apply the same value to “all edges on the path from vertex \(u\) to \(v\)” on the MST. Using Heavy-Light Decomposition (HLD), we can decompose any tree path into \(O(\log N)\) contiguous intervals (on an array).

Implementation details: - For each vertex \(v (\neq \text{root})\), store the weight of the edge to its parent as pw[v]. - Using HLD’s pos[v], treat the “edge to parent” as one element of the array.
Specifically, edge (parent[v], v) corresponds to position pos[v] (root is an exception).

Step 3: Process non-tree edges in ascending weight order, filling minimum replacement weights for “undetermined edges” on each path

The goal is: - For each MST edge \(e\), find the “minimum replacement weight” repl[e].

The procedure: 1. Sort non-tree edges \((u,v,w)\) in ascending order of weight. 2. The cycle formed by a non-tree edge = the path \(u \to v\) on the MST. Each MST edge on this path has \(w\) as a replacement candidate. 3. Since we want the minimum, we only want to assign \(w\) to edges whose repl has not yet been determined.

The key technique here is to efficiently “fill only undetermined positions” in array intervals, using a Union-Find-like structure nxt that points to the “next undetermined position.”

• paint(l, r, w): Among positions in interval \([l,r]\), assign repl = w only to undetermined positions, and make filled positions skippable via nxt.
• Since non-tree edges are processed in ascending weight order, the first value assigned to each position is the minimum replacement weight for that edge.

Since HLD decomposes a path into multiple intervals, we call paint for each interval.

Step 4: Compute “MST cost when each MST edge is cut” and take the maximum

For each MST edge (parent[v], v) (corresponding to each vertex v other than root): - The edge weight is pw[v] - The minimum replacement weight is repl[pos[v]]

So the MST cost after cutting is: [ T - pw[v] + repl[pos[v]] ] We maximize this over all \(v=1..N-1\), and since cutting a non-MST edge gives cost \(T\), the final answer is the maximum among all these values.

Note that due to the problem’s condition of “2-edge-connectivity,” every MST edge has a guaranteed replacement edge, so repl is always finite.

Complexity

• Time complexity:
  
  • Kruskal: \(O(M \log M)\)
    
  • HLD construction: \(O(N)\)
    
  • Non-tree edge processing: path decomposition yields \(O(\log N)\) intervals, but paint fills each position at most once, so the total is approximately \(O((N + M)\alpha(N) + M \log N)\)
    Overall, approximately: [ O(M \log M + M \log N) ]
• Space complexity: \(O(N + M)\)

Implementation Notes

• Edge-to-array-position mapping: pos[v] represents the edge to parent rather than “vertex v itself” (root has no corresponding edge and is treated as an exception).

• Excluding the LCA edge in path updates: Within the same heavy-path, the final step uses l = pos[v] + 1 to avoid erroneously including the “edge to parent” on the LCA side.

• Skipping via nxt: paint is a classic technique for “filling only undetermined positions,” preventing what would otherwise be \(O(NM)\) if intervals were naively painted.

• Handling root: repl[pos[root]] is never used, so it is treated as already filled from the start and skipped.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.