問題
$N$ 頂点 $M$ 辺の連結な無向グラフが与えられる。このグラフは cactus グラフ（どの辺も高々1つの単純閉路にしか属さない）であることが保証されている。各頂点 $i$ には重み $w_i$ が定められている。
グラフから頂点の部分集合を選び、選んだ頂点同士がどの2つも辺で直接結ばれていない（独立集合である）という条件のもとで、選んだ頂点の重みの総和を最大化せよ。
入力形式
N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
:
u_M v_M制約
$2 \le N \le 2000$
$N-1 \le M \le \lfloor 3(N-1)/2 \rfloor$
連結かつ cactus（辺は高々1つの単純閉路に属す）
$1 \le w_i \le 10^9$
自己ループ・多重辺なし
入出力例
入力例1
3 3
3 5 4
1 2
2 3
3 1出力例1
5入力例2
4 4
10 1 10 1
1 2
2 3
3 4
4 1出力例2
20概念図
ヒント（段階的開示）
ヒント1（方向性）
木の上での最大重み独立集合（隣接頂点DP：「その頂点を選ぶ場合／選ばない場合」の2状態を子から親へマージする）はおなじみのDPである。cactus グラフはこの「木」に「単純閉路」が混じったものと考えられる。閉路が絡む部分だけ特別な処理を挟み、それ以外は通常の木DPと同じように扱えないか、と考えるのが出発点になる。
ヒント2（アプローチ）
cactus グラフを二重連結成分（BCC）ごとに分解すると、各BCCは「橋（辺1本）」か「単純閉路」のどちらかになる。この分解によって得られる「ブロック木」は木構造そのものになる。橋でつながる部分は通常の木DPのマージ規則を使い、閉路でつながる部分は「閉路を1点で切り開いた鎖」とみなして環状DP特有の処理を行う。
ヒント3（誘導）
def dfs(u, pedge):
disc[u] = low[u] = timer[0]; timer[0] += 1
for v, eid in adj[u]:
if eid == pedge:
continue
if not visited[v]:
visited[v] = True
edge_stack.append(eid)
dfs(v, eid)
low[u] = min(low[u], low[v])
if low[v] >= disc[u]:
# ここでBCCが1つ確定する（辺スタックから eid まで pop）
...
elif disc[v] < disc[u]:
edge_stack.append(eid)
low[u] = min(low[u], disc[v])閉路 $v_0(=$ 起点$), v_1, \dots, v_{k-1}$ に対して、起点を選ぶ場合は $v_1$ と $v_{k-1}$（両端）を強制的に除外した鎖DP、選ばない場合は両端自由の鎖DPで解く（house robber on a circle の一般化）。
模範解答 (Python)
import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
m = int(data[idx]); idx += 1
w = [0] * (n + 1)
for i in range(1, n + 1):
w[i] = int(data[idx]); idx += 1
adj = [[] for _ in range(n + 1)]
edges = []
for eid in range(m):
u = int(data[idx]); idx += 1
v = int(data[idx]); idx += 1
adj[u].append((v, eid))
adj[v].append((u, eid))
edges.append((u, v))
disc = [0] * (n + 1)
low = [0] * (n + 1)
visited = [False] * (n + 1)
timer = [1]
edge_stack = []
bccs = [] # list of list of edge ids
def dfs_bcc(u, pedge):
visited[u] = True
disc[u] = low[u] = timer[0]
timer[0] += 1
for v, eid in adj[u]:
if eid == pedge:
continue
if not visited[v]:
edge_stack.append(eid)
dfs_bcc(v, eid)
low[u] = min(low[u], low[v])
if low[v] >= disc[u]:
comp = []
while True:
e = edge_stack.pop()
comp.append(e)
if e == eid:
break
bccs.append(comp)
elif disc[v] < disc[u]:
edge_stack.append(eid)
low[u] = min(low[u], disc[v])
dfs_bcc(1, -1)
children_bridge = [[] for _ in range(n + 1)]
cycles_of = [[] for _ in range(n + 1)]
for comp in bccs:
if len(comp) == 1:
u, v = edges[comp[0]]
# 親側（discが小さい方）から子側へ
if disc[u] < disc[v]:
children_bridge[u].append(v)
else:
children_bridge[v].append(u)
else:
vs = set()
local_adj = {}
for eid in comp:
a, b = edges[eid]
vs.add(a); vs.add(b)
local_adj.setdefault(a, []).append(b)
local_adj.setdefault(b, []).append(a)
entry = min(vs, key=lambda x: disc[x])
ring = [entry]
prev = None
cur = entry
nxt = local_adj[cur][0]
while nxt != entry:
ring.append(nxt)
prev, cur = cur, nxt
n0, n1 = local_adj[cur]
nxt = n0 if n0 != prev else n1
cycles_of[entry].append(ring[1:])
dp0 = [0] * (n + 1)
dp1 = [0] * (n + 1)
NEG = float('-inf')
def chain_dp(chain, force_first, force_last):
vals0 = [dp0[v] for v in chain]
vals1 = [dp1[v] for v in chain]
if force_first:
vals1[0] = NEG
if force_last:
vals1[-1] = NEG
prev0, prev1 = vals0[0], vals1[0]
for i in range(1, len(chain)):
cur0 = max(prev0, prev1) + vals0[i]
cur1 = (prev0 + vals1[i]) if vals1[i] != NEG else NEG
prev0, prev1 = cur0, cur1
return max(prev0, prev1)
def compute(u):
dp0[u] = 0
dp1[u] = w[u]
for c in children_bridge[u]:
compute(c)
dp0[u] += max(dp0[c], dp1[c])
dp1[u] += dp0[c]
for chain in cycles_of[u]:
for v in chain:
compute(v)
case_a = chain_dp(chain, True, True) # u を選ぶ
case_b = chain_dp(chain, False, False) # u を選ばない
dp1[u] += case_a
dp0[u] += case_b
compute(1)
print(max(dp0[1], dp1[1]))
main()Step-by-Step 解説
1cactus のBCC分解は「橋」か「単純閉路」の2種類のみ
cactus の定義（どの辺も高々1つの単純閉路にしか属さない）から、任意の二重連結成分は「辺1本（橋）」か「単純閉路そのもの」のどちらかになる。これによりTarjanの標準的なBCC分解アルゴリズムをそのまま適用でき、各BCCの種類分岐が単純になる。
cactus の定義（どの辺も高々1つの単純閉路にしか属さない）から、任意の二重連結成分は「辺1本（橋）」か「単純閉路そのもの」のどちらかになる。これによりTarjanの標準的なBCC分解アルゴリズムをそのまま適用でき、各BCCの種類分岐が単純になる。
2ブロック木は木構造
橋と閉路を「ブロック」として1つの単位に潰すと、ブロック同士の接続関係は木構造（ブロック木）になる。本問ではブロック木を明示的なノードとして作らず、「橋でつながる子」と「閉路でつながる子の並び」という2種類の情報として頂点に直接埋め込むことで実装を簡略化している。
橋と閉路を「ブロック」として1つの単位に潰すと、ブロック同士の接続関係は木構造（ブロック木）になる。本問ではブロック木を明示的なノードとして作らず、「橋でつながる子」と「閉路でつながる子の並び」という2種類の情報として頂点に直接埋め込むことで実装を簡略化している。
3閉路のDPは「起点を切って鎖にする」
閉路 $v_0,\dots,v_{k-1}$ の最大重み独立集合は、$v_0$ を選ぶ場合と選ばない場合の2通りに分けて、残りを鎖として解く。$v_i$ の dp0/dp1 は「その閉路以外の部分木からの寄与だけを先に含んだ値」であることに注意（compute(v) を先に呼んでから鎖DPに使う）。
閉路 $v_0,\dots,v_{k-1}$ の最大重み独立集合は、$v_0$ を選ぶ場合と選ばない場合の2通りに分けて、残りを鎖として解く。$v_i$ の dp0/dp1 は「その閉路以外の部分木からの寄与だけを先に含んだ値」であることに注意（compute(v) を先に呼んでから鎖DPに使う）。
4入力例2（4頂点の閉路）の検算
重み(10,1,10,1)の4頂点閉路では、独立集合として選べる最大の組み合わせは「頂点1と頂点3」で合計20。DPが正しく20を出せることは、起点を選ぶケースで両端を除外した鎖DPの中で頂点3（重み10）が選ばれることに対応する。
重み(10,1,10,1)の4頂点閉路では、独立集合として選べる最大の組み合わせは「頂点1と頂点3」で合計20。DPが正しく20を出せることは、起点を選ぶケースで両端を除外した鎖DPの中で頂点3（重み10）が選ばれることに対応する。
5計算量
BCC分解は $O(N+M)$。ブロック木DPも各頂点・各辺を定数回しか処理しないため $O(N+M)$。ただし本問の模範解答は再帰を用いており、$N$ を $2\times10^5$ 規模まで扱うには反復（明示的スタック）への書き換えが必要。
BCC分解は $O(N+M)$。ブロック木DPも各頂点・各辺を定数回しか処理しないため $O(N+M)$。ただし本問の模範解答は再帰を用いており、$N$ を $2\times10^5$ 規模まで扱うには反復（明示的スタック）への書き換えが必要。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 鎖DPの「選ばない」遷移で vals0[i] の加算を忘れる（cur0 = max(prev0, prev1) のまま） | 「選ばない」＝「何も加算しない」という単純な独立集合DPのイメージに引きずられる | cur0 = max(prev0, prev1) + vals0[i] とし、選ばない場合でも閉路外部分木の寄与を必ず加算する。閉路上の頂点が全て葉の例だけで検証すると見逃しやすい |
| 閉路DPで両端の除外を忘れる（起点を選ぶケース） | 単純な鎖DPと環状DPの違いを意識しない | 起点を選ぶ場合は、閉路上で起点に隣接する2頂点（鎖の両端）を強制的に「選ばない」状態に固定する |
| dp0[v]/dp1[v] を閉路DPの前に確定させず、閉路の重みだけで計算してしまう | 閉路上の頂点がさらに別の部分木（橋でつながる子）を持つケースを見落とす | 鎖DPを行う前に、必ずその閉路上の各頂点で compute(v) を先に呼ぶ |
| BCCの判定で low[v] >= disc[u] の意味を取り違える | 橋の判定条件と二重連結成分の切り出し条件を混同する | 二重連結成分の切り出しは low[v] >= disc[u]（等号を含む）を使う。橋か閉路かは切り出された成分の辺数で事後的に判定する |
| 閉路の頂点順序（リング順）を辺集合からそのまま作らず、頂点集合の順序で扱ってしまう | local_adj を作らずに集合の順序をそのまま使う | 必ず local_adj に沿って隣接を辿り、実際の閉路の順序（リング）を再構築する |
次のステップ
- 発展: 本問の制約を $N\le2\times10^5$ まで引き上げ、BCC分解と compute の両方を明示的スタックによる反復DFSに書き換えて計算量 $O(N+M)$ を実測せよ。
- 発展2: 「最大重み独立集合」ではなく「頂点被覆」や「彩色数」など、cactus グラフ上で同様にブロック木DPが適用できる他の問題を1つ選び、DPの状態設計を1から作り直してみよ。