Day 167-Q4 — 2026-10-01 | サボテングラフの最大重み独立集合（閉路を鎖にして畳む。両端を選べない場合を別に持つ）

📋 コピーimport sys
def solve(n, w, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    parent = [-1]*n; depth = [-1]*n; order = []
    depth[0] = 0
    stack = [0]; it = [0]*n
    order.append(0)
    back = []                                  # (子孫 b, 祖先 a)
    while stack:
        v = stack[-1]
        if it[v] < len(adj[v]):
            u = adj[v][it[v]]; it[v] += 1
            if depth[u] == -1:
                depth[u] = depth[v]+1; parent[u] = v
                order.append(u); stack.append(u)
            elif u != parent[v] and depth[u] < depth[v]:
                back.append((v, u))            # 後退辺（単純グラフなので親との重複は無い）
        else:
            stack.pop()
    in_cycle = [False]*n                       # 親への辺が閉路に属するか
    cycles = [[] for _ in range(n)]            # 頂点 a を頂上とする閉路の鎖 [c1..ck]（a の子側から）
    for b, a in back:
        chain = []; x = b
        while x != a:
            chain.append(x); in_cycle[x] = True; x = parent[x]
        chain.reverse()
        cycles[a].append(chain)
    d0 = [0]*n; d1 = [w[v] for v in range(n)]  # d0: v を選ばない / d1: 選ぶ（v の「閉路を除く」下側だけ）
    NEG = float('-inf')
    for v in reversed(order):
        # この時点で d0[v], d1[v] には「橋の子」の分が入っている。頂上が v の閉路を畳む
        for chain in cycles[v]:
            for fix_ends in (False, True):
                # 鎖上の独立集合の最大値。fix_ends なら両端 c1, ck は選べない（v を選ぶ場合）
                s0 = d0[chain[0]]                       # c1 を選ばない
                s1 = NEG if fix_ends else d1[chain[0]]  # c1 を選ぶ
                for c in chain[1:]:
                    n0 = max(s0, s1) + d0[c]
                    n1 = s0 + d1[c]
                    s0, s1 = n0, n1
                if fix_ends: val = s0
                else: val = max(s0, s1)
                if fix_ends: d1[v] += val
                else: d0[v] += val
            # fix_ends=True の値は ck を選べない: s0 は「ck を選ばない」なので OK
        p = parent[v]
        if p != -1 and not in_cycle[v]:
            d1[p] += d0[v]
            d0[p] += max(d0[v], d1[v])
    return max(d0[0], d1[0])
def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    w = [int(x) for x in data[2:2+n]]
    edges = [(int(data[2+n+2*i])-1, int(data[3+n+2*i])-1) for i in range(m)]
    print(solve(n, w, edges))
if __name__ == "__main__": main()