Day 009-Q5 — Link-Cut Tree

問題

$N$ 頂点の森。$Q$ 個のクエリを処理せよ。

• link u v w : 頂点 $u$ と $v$ の間に重み $w$ の辺を追加
• cut u v : 辺を削除
• query u v : 連結なら経路上の辺の重みの最大値、非連結なら Not Connected

制約

入出力例

5 6
link 1 2 3
link 2 3 5
link 3 4 2
query 1 4
cut 2 3
query 1 4

5
Not Connected

ヒント (段階的開示)

模範解答 (Python)

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

class Node:
    __slots__ = ['ch', 'par', 'val', 'max_val', 'rev']
    def __init__(self, val=0):
        self.ch = [None, None]
        self.par = None
        self.val = val
        self.max_val = val
        self.rev = False

class LCT:
    def __init__(self, n):
        self.nodes = [Node() for _ in range(n + 1)]

    def is_root(self, v):
        p = v.par
        return p is None or (p.ch[0] is not v and p.ch[1] is not v)

    def pull(self, v):
        v.max_val = v.val
        for c in v.ch:
            if c:
                v.max_val = max(v.max_val, c.max_val)

    def push(self, v):
        if v.rev:
            v.ch[0], v.ch[1] = v.ch[1], v.ch[0]
            for c in v.ch:
                if c:
                    c.rev ^= True
            v.rev = False

    def rotate(self, v):
        p = v.par
        g = p.par
        d = 1 if p.ch[1] is v else 0
        c = v.ch[1 - d]
        if not self.is_root(p):
            if g.ch[0] is p: g.ch[0] = v
            elif g.ch[1] is p: g.ch[1] = v
        v.par = g
        p.ch[d] = c
        if c: c.par = p
        v.ch[1 - d] = p
        p.par = v
        self.pull(p)
        self.pull(v)

    def splay(self, v):
        path = [v]
        u = v
        while not self.is_root(u):
            u = u.par
            path.append(u)
        for u in reversed(path):
            self.push(u)
        while not self.is_root(v):
            p = v.par
            if not self.is_root(p):
                g = p.par
                if (g.ch[0] is p) == (p.ch[0] is v):
                    self.rotate(p)
                else:
                    self.rotate(v)
            self.rotate(v)

    def access(self, v):
        last = None
        u = v
        while u:
            self.splay(u)
            u.ch[1] = last
            self.pull(u)
            last = u
            u = u.par
        self.splay(v)

    def make_root(self, v):
        self.access(v)
        v.rev ^= True
        self.push(v)

    def find_root(self, v):
        self.access(v)
        while v.ch[0]:
            self.push(v)
            v = v.ch[0]
        self.splay(v)
        return v

    def link(self, u, v):
        self.make_root(u)
        u.par = v

    def cut(self, u, v):
        self.make_root(u)
        self.access(v)
        v.ch[0].par = None
        v.ch[0] = None
        self.pull(v)

    def query_path_max(self, u, v):
        self.make_root(u)
        self.access(v)
        return v.max_val

    def connected(self, u, v):
        return self.find_root(u) is self.find_root(v)

def solve():
    N, Q = map(int, input().split())
    lct = LCT(N)
    edge_nodes = {}
    extra = [Node() for _ in range(Q)]

    out = []
    for qi in range(Q):
        line = input().split()
        if line[0] == 'link':
            u, v, w = int(line[1]), int(line[2]), int(line[3])
            e = extra[qi]
            e.val = w
            e.max_val = w
            eid = (min(u, v), max(u, v))
            edge_nodes[eid] = e
            lct.link(lct.nodes[u], e)
            lct.link(e, lct.nodes[v])
        elif line[0] == 'cut':
            u, v = int(line[1]), int(line[2])
            eid = (min(u, v), max(u, v))
            e = edge_nodes.pop(eid)
            lct.cut(lct.nodes[u], e)
            lct.cut(e, lct.nodes[v])
        else:
            u, v = int(line[1]), int(line[2])
            nu, nv = lct.nodes[u], lct.nodes[v]
            if not lct.connected(nu, nv):
                out.append("Not Connected")
            else:
                out.append(str(lct.query_path_max(nu, nv)))

    print('\n'.join(out))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展問題: 動的木上の辺の更新クエリ
• Euler Tour Tree との比較

自己評価

自分の回答

気づき・メモ