Day 057-Q3 — 動的フォレスト辺管理（Link-Cut Tree）

問題

$N$ 頂点の動的フォレスト（初期は全て孤立頂点）に対し、以下の $Q$ クエリをオンラインで処理せよ。

• L u v: 辺 $(u, v)$ を追加する（フォレスト性が保たれる）
• C u v: 辺 $(u, v)$ を削除する（この辺は存在する）
• D u: 頂点 $u$ の次数（現在接続されている辺の本数）を出力する
• E v: 頂点 $v$ が属する木の辺の本数を出力する

入出力例

5 8
L 1 2
L 2 3
L 3 4
D 2
E 1
C 2 3
D 2
E 1

2
3
1
1

辺追加後: {1-2, 2-3, 3-4}。D 2=2（辺1-2, 2-3）。E 1=3辺。C 2-3 削除後: {1-2}と{3-4}。D 2=1。E 1=1辺。

概念図: Link-Cut Tree の仮想辺管理

ヒント（段階的開示）

def link(u, v):
    expose(v); expose(u)
    par[v] = u
    vsize[u] += size[v]
    upd(u)

def tree_size(v):
    expose(v)
    return size[v]  # 頂点数（辺数 = これ - 1）

# クエリ E v の処理:
# out.append(str(tree_size(v) - 1))

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def solve():
    sys.setrecursionlimit(300000)
    N, Q = map(int, input().split())

    ch = [[0, 0] for _ in range(N+1)]
    par = [0] * (N+1)
    rev = [False] * (N+1)
    sz = [1] * (N+1)
    vsize = [0] * (N+1)
    deg = [0] * (N+1)

    def is_root(v):
        p = par[v]
        return p == 0 or (ch[p][0] != v and ch[p][1] != v)

    def push(v):
        if rev[v]:
            l, r = ch[v]
            ch[v][0], ch[v][1] = r, l
            if l: rev[l] ^= True
            if r: rev[r] ^= True
            rev[v] = False

    def upd(v):
        l, r = ch[v]
        sl = sz[l] if l else 0
        sr = sz[r] if r else 0
        sz[v] = sl + sr + vsize[v] + 1

    def rotate(v):
        p = par[v]; g = par[p]
        d = 1 if ch[p][1] == v else 0
        c = ch[v][1-d]
        if not is_root(p):
            if ch[g][0] == p: ch[g][0] = v
            else: ch[g][1] = v
        par[v] = g
        ch[v][1-d] = p; par[p] = v
        ch[p][d] = c
        if c: par[c] = p
        upd(p); upd(v)

    def splay(v):
        stack = [v]; u = v
        while not is_root(u):
            u = par[u]; stack.append(u)
        while stack: push(stack.pop())
        while not is_root(v):
            p = par[v]
            if not is_root(p):
                g = par[p]
                if (ch[g][0]==p) == (ch[p][0]==v): rotate(p)
                else: rotate(v)
            rotate(v)

    def expose(v):
        last = 0; u = v
        while u:
            splay(u)
            c = ch[u][1]
            if c: vsize[u] += sz[c]; ch[u][1] = 0; par[c] = u; upd(u)
            if last: vsize[u] -= sz[last]; ch[u][1] = last; par[last] = u; upd(u)
            last = u; u = par[u]
        splay(v); return last

    def link(u, v):
        expose(v); expose(u)
        par[v] = u; vsize[u] += sz[v]; upd(u)

    def cut_edge(u, v):
        expose(v); splay(u); expose(v)
        ch[v][0] = 0; par[u] = 0; upd(v)

    def tree_size(v):
        expose(v); return sz[v]

    out = []
    for _ in range(Q):
        line = input().split()
        op = line[0]
        if op == 'L':
            u, v = int(line[1]), int(line[2])
            link(u, v); deg[u] += 1; deg[v] += 1
        elif op == 'C':
            u, v = int(line[1]), int(line[2])
            cut_edge(u, v); deg[u] -= 1; deg[v] -= 1
        elif op == 'D':
            out.append(str(deg[int(line[1])]))
        elif op == 'E':
            out.append(str(tree_size(int(line[1])) - 1))
    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: Link-Cut Tree の基本構造

各木を「補助木（splay tree）のチェーン」に分解。expose(v) は $v$ から根への経路を一本の補助木に整理し、パス上のクエリを $O(\log N)$ で処理可能にする。

Step 2: 仮想辺サイズ管理

各ノードの vsize に「仮想辺で繋がっている子のサイズ合計」を蓄積することで、tree_size(v) = expose(v) 後の size[v] が木全体の頂点数になる。辺数 = 頂点数 - 1。

Step 3: 次数管理

LCT の構造から次数を取り出すのは複雑なため、別の配列 deg[u] で管理し link/cut 時に増減させる。

Step 4: cut 操作

expose(v) で $v$ を根の状態にした後、v の左子が切断対象 $u$ になるよう splay し、子を切り離す。

計算量

よくあるミス

次のステップ

• 発展: LCT + パス上の最小辺重み（動的最小全域木の管理）
• 類題: AIZU JUDGE 2667 "Tree"、Codeforces 117E
• 応用: LCT で木のパス上の XOR 和クエリ

自己評価