Day 061-Q2 | Dominator Tree + クエリ（Lengauer-Tarjan）

問題

$N$ 頂点 $M$ 辺の有向グラフ $G$ と始点 $s$ が与えられる。

頂点 $d$ が頂点 $v$ を支配するとは、$s$ から $v$ への全てのパスが $d$ を通ることをいう。

以下の $Q$ 個のクエリに答えよ：

sub v: 支配木において $v$ を根とする部分木に含まれる頂点の個数を出力せよ
dom u v: 頂点 $u$ が頂点 $v$ を支配するか判定せよ（Yes/No）

制約

パラメータ	範囲
$N$	$2 \le N \le 2 \times 10^5$
$M$	$1 \le M \le 5 \times 10^5$
$Q$	$1 \le Q \le 2 \times 10^5$
クエリの $v, u$	$s$ から到達可能な頂点

入出力例

入力例 1

出力例 1

6
3
Yes

支配木: 0→1, 0→2, 0→3（3は1→3と2→3の両方から到達可能なため0が直接支配）, 3→4, 3→5。sub(0)=6（全頂点）, sub(3)=3（3,4,5）, dom(0,5)=Yes（0は全頂点を支配）。

概念図: 有向グラフと支配木

ヒント（段階的開示）

ヒント1: 方向性

Lengauer-Tarjan アルゴリズムで支配木を $O(M \alpha(N))$ で構築する。その後クエリは Euler Tour + Euler 時刻の比較で $O(1)$ で処理できる。

ヒント2: アプローチ

半支配者 (Semi-dominator): DFS 番号が小さい頂点 $v$ で $v$→$w$ へ「$w$ より大きい番号の頂点のみ経由」して到達できるものの最小
即時支配者 (Immediate Dominator): 半支配者と Union-Find の path compression で決定
支配木構築後、sub v = Euler Tour の tin[v]〜tout[v] の範囲に含まれる葉の数 = (tout[v]-tin[v]+1)//2+1 など
dom u v = tin[u] ≤ tin[v] かつ tout[v] ≤ tout[u]

ヒント3: コード骨格

# 支配木のEuler Tour
tin = [0]*N; tout = [0]*N; timer = [0]
stk = [(root, False)]
while stk:
    v, leaving = stk.pop()
    if leaving:
        tout[v] = timer[0]; timer[0] += 1
    else:
        tin[v] = timer[0]; timer[0] += 1
        stk.append((v, True))
        for c in dom_children[v]:
            stk.append((c, False))

# dom u v
def is_ancestor(u, v):
    return tin[u] <= tin[v] and tout[v] <= tout[u]

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(400000)

def main():
    N, M, s = map(int, input().split())
    adj  = [[] for _ in range(N)]
    radj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v); radj[v].append(u)

    # ---- Lengauer-Tarjan ----
    order2 = []; dfnum2 = [-1]*N; par2 = [-1]*N; cnt = [0]
    stk2 = [(s, iter(adj[s]))]
    dfnum2[s] = 0; cnt[0] = 1; order2.append(s)
    while stk2:
        v, it = stk2[-1]
        try:
            w = next(it)
            if dfnum2[w] == -1:
                dfnum2[w] = cnt[0]; cnt[0] += 1
                par2[w] = v; order2.append(w)
                stk2.append((w, iter(adj[w])))
        except StopIteration:
            stk2.pop()
    nn = len(order2)

    semi2 = list(range(N)); idom2 = [-1]*N
    bucket2 = [[] for _ in range(N)]
    anc2 = list(range(N)); lab2 = list(range(N))

    def compress(v):
        if anc2[anc2[v]] != anc2[v]:
            compress(anc2[v])
            if dfnum2[semi2[lab2[anc2[v]]]] < dfnum2[semi2[lab2[v]]]:
                lab2[v] = lab2[anc2[v]]
            anc2[v] = anc2[anc2[v]]

    def eval2(v):
        if anc2[v] == v: return v
        compress(v); return lab2[v]

    for i in range(nn-1, 0, -1):
        w = order2[i]
        for v in radj[w]:
            if dfnum2[v] == -1: continue
            u = eval2(v)
            if dfnum2[semi2[u]] < dfnum2[semi2[w]]: semi2[w] = semi2[u]
        bucket2[semi2[w]].append(w)
        anc2[w] = par2[w]
        for v in bucket2[par2[w]]:
            u = eval2(v)
            idom2[v] = par2[w] if semi2[u] == semi2[v] else u
        bucket2[par2[w]] = []

    for i in range(1, nn):
        w = order2[i]
        if idom2[w] != semi2[w]: idom2[w] = idom2[idom2[w]]
    idom2[s] = s

    # Build dominator tree children
    dom_ch = [[] for _ in range(N)]
    for v in order2:
        if v != s: dom_ch[idom2[v]].append(v)

    # Euler Tour (iterative)
    tin = [0]*N; tout = [0]*N; timer = [0]
    sub_size = [0]*N
    stk3 = [(s, False)]
    while stk3:
        v, leaving = stk3.pop()
        if leaving:
            tout[v] = timer[0]; timer[0] += 1
            sub_size[v] = (tout[v] - tin[v] + 1) // 2
        else:
            tin[v] = timer[0]; timer[0] += 1
            stk3.append((v, True))
            for c in dom_ch[v]: stk3.append((c, False))

    Q = int(input())
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'sub':
            v = int(line[1])
            out.append(str(sub_size[v]))
        else:
            u, v = int(line[1]), int(line[2])
            if tin[u] <= tin[v] and tout[v] <= tout[u]:
                out.append("Yes")
            else:
                out.append("No")
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: DFS 順番付け

始点 $s$ から DFS し、各頂点に DFS 番号 dfnum を付与。配列 order2 に訪問順を記録。逆順処理 (i=nn-1 → 1) のためのポイント。

Step 2: 半支配者計算

逆 DFS 順で各頂点 $w$ を処理。$w$ に入る辺の始点 $v$ から eval(v) を求め、semi[v] の最小を semi[w] とする。Union-Find (path compression) で $O(\log N)$。

Step 3: 即時支配者の確定

bucket に semi が確定した頂点を蓄積し、親 par[w] にまとめて処理。後処理ループで idom[w] != semi[w] のとき idom[w] = idom[idom[w]] で最終確定。

Step 4: Euler Tour + クエリ

支配木を Euler Tour し、tin/tout を記録。sub v = (tout[v]-tin[v]+1)//2（各ノードが入退2スタンプを消費）。dom u v = u が v の祖先かどうか。

よくあるミス

ミス	原因	正しい書き方
compress の再帰が深い	Python の再帰限度	sys.setrecursionlimit(400000) または反復版
到達不能頂点の処理	radj に DFS 外の頂点が入る	`if dfnum2[v] == -1: continue`
tin/tout 比較が逆	out の方が大きいと思い込む	tin[u] ≤ tin[v] かつ tout[v] ≤ tout[u] が「u が祖先」
bucket 処理の順序が逆	Step3 を Step2 より先にやる	semi 確定 → link → bucket 処理の順を守る

次のステップ

発展問題: オンライン辺追加のある動的支配木（Link-Cut Tree 応用）
関連: SCC 分解 + 凝縮 DAG 上の支配木との組み合わせ

自己評価

完全理解おおむね理解要復習