Day 042-Q2 — Black-White 辺着色 + Matroid Union（2色全域木）

2026-05-25 赤色 Master / Phase 8+ ★★★★★★★★★ Matroid Intersection / Kruskal 双方向

問題

$N$ 頂点 $M$ 辺の無向グラフで各辺が黒 $(c=0)$ か白 $(c=1)$ に着色されている。黒辺 $\le B$ 本・白辺 $\le W$ 本でスパニングツリーを構成できるか判定し、可能なら黒辺最小の本数と白辺本数を出力せよ。

制約

$2 \le N \le 2 \times 10^5$
$N-1 \le M \le 3 \times 10^5$
$0 \le B, W \le N-1$
時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

4 5 2 3
1 2 0
2 3 0
3 4 1
1 4 1
2 4 0

出力例 1

Yes 2 1

概念図: 実現可能な黒辺数の区間

黒辺数 b 0 N-1 b_min b_max 実現可能区間 [b_min, b_max] B (黒辺上限) N-1-W (黒辺下限) 有効範囲 [lo, hi]

ヒント（段階的開示）

ヒント1: 方向性
スパニングツリーで使う黒辺数 $b$ は連続した整数区間 $[b_{\min}, b_{\max}]$ をとる（Matroid Exchange Lemma）。制約 $b \le B$ かつ $b \ge N-1-W$ との交点を求めるだけでよい。
ヒント2: アプローチ
  1. 黒辺優先 Kruskal で $b_{\max}$（黒辺を最大化）
  2. 白辺優先 Kruskal で $b_{\min}$（黒辺を最小化）
  3. 制約との交点: $lo = \max(b_{\min}, N-1-W)$, $hi = \min(b_{\max}, B)$
  4. $lo \le hi$ なら Yes、黒辺 $lo$ 本で出力
ヒント3: 実装骨格 
def kruskal(prefer_black):
    # prefer_black=True: 黒辺(c=0)を優先してソート
    uf = UF(N)
    bc = wc = 0
    key = lambda e: e[2] if prefer_black else -e[2]
    for u, v, c in sorted(edges, key=key):
        if uf.union(u, v):
            if c == 0: bc += 1
            else: wc += 1
    total = bc + wc
    return bc, total  # 使用黒辺数, 総辺数

max_b, t1 = kruskal(True)
min_b, t2 = kruskal(False)
if t1 < N-1: # スパニングツリー不成立
    print("No"); return
lo = max(min_b, N-1-W)
hi = min(max_b, B)
if lo > hi: print("No")
else: print(f"Yes {lo} {N-1-lo}")

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, M, B, W = int(data[idx]), int(data[idx+1]), int(data[idx+2]), int(data[idx+3])
    idx += 4
    edges = []
    for _ in range(M):
        u, v, c = int(data[idx])-1, int(data[idx+1])-1, int(data[idx+2])
        edges.append((u, v, c))
        idx += 3

    class UF:
        def __init__(self, n):
            self.p = list(range(n))
            self.r = [0] * n
        def find(self, x):
            while self.p[x] != x:
                self.p[x] = self.p[self.p[x]]
                x = self.p[x]
            return x
        def union(self, x, y):
            x, y = self.find(x), self.find(y)
            if x == y: return False
            if self.r[x] < self.r[y]: x, y = y, x
            self.p[y] = x
            if self.r[x] == self.r[y]: self.r[x] += 1
            return True

    def kruskal_count(prefer_black):
        uf = UF(N)
        bc = wc = 0
        for u, v, c in sorted(edges, key=lambda e: e[2] if prefer_black else -e[2]):
            if uf.union(u, v):
                if c == 0: bc += 1
                else: wc += 1
        return bc, bc + wc

    max_b, total = kruskal_count(True)
    if total < N - 1:
        print("No")
        return

    min_b, _ = kruskal_count(False)

    lo = max(min_b, N - 1 - W)
    hi = min(max_b, B)

    if lo > hi:
        print("No")
    else:
        print(f"Yes {lo} {N-1-lo}")

solve()

Step-by-Step 解説

1Matroid Exchange Lemma
グラフマトロイドでは、2つの基（スパニングツリー）$T_1, T_2$ が存在すれば、$T_1$ から辺を1本除き $T_2$ から1本追加して新しい基を作れる。この交換の繰り返しで黒辺数を連続的に変化させられる → 実現可能な黒辺数は連続区間。
2黒辺優先 Kruskal
辺を $c=0$（黒）優先でソート（黒辺は白辺より先に選ばれる）して Kruskal を実行。得られた木は黒辺数 $b_{\max}$ の木。
3白辺優先 Kruskal
同様に $c=1$ 優先でソートすると黒辺数 $b_{\min}$ の木が得られる。
4制約との交点
制約 $b \le B$ と白辺数 $N-1-b \le W$（→ $b \ge N-1-W$）を合わせると有効範囲 $[lo, hi]$。空集合なら No。

計算量

Kruskal ソート: $O(M \log M)$
Union-Find: $O(M \cdot \alpha(N)) \approx O(M)$
合計: $O(M \log M)$（Kruskal 2回）

よくあるミス

ミス原因正しい書き方
連続性の仮定漏れExchange Lemma を知らない区間 [lo, hi] で判定する
グラフ非連結のケースtotal < N-1 の確認忘れKruskal の総辺数をチェック
白辺の上限 W の変換ミスb + (N-1-b) = N-1 の関係b >= N-1-W として下限に変換

次のステップ

  • 発展問題: 3色辺で各色 $\le k$ 本のスパニングツリー（Matroid Intersection 一般化）
  • 類題: AtCoder ARC 076 D "Built?"
  • 応用: 重み付き Matroid Intersection（最小重みの色制約スパニングツリー）

自己評価