概要

根付き木において、各頂点に対し、その頂点を根とする部分木に関する特性を求めるためのテクニック

計算量

木の頂点数を \(N\) とする。

特性を計算するためのデータ構造への1頂点の追加に \(O(A)\), 1頂点の削除に \(O(B)\) 、1頂点ごとにクエリ処理に \(O(C)\) かかる場合

\(O(N (A + B) \log N + NC)\)

実装

def dsu_on_tree(N, G, Prop):
    order = []
    prt = [-1]*N

    que = [0]
    pn = [-1]*N
    used = [0]*N
    used[0] = 1
    while que:
        v = que.pop()
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            prt[w] = v
        pn[v] = len(order)
        order.append(v)

    sz = [0]*N
    tmp_ps = [[i] for i in range(N)]
    # heavy paths
    h_ps = []
    for v in reversed(order):
        p = prt[v]
        m_sz = 0
        h = -1
        s = 1
        for w in G[v]:
            if p == w:
                continue
            if m_sz < sz[w]:
                m_sz = sz[w]
                h = w
            s += sz[w]
        if h != -1:
            tmp_ps[v] = tmp_ps[h]
            tmp_ps[v].append(v)
            for w in G[v]:
                if w == p or w == h:
                    continue
                h_ps.append(tmp_ps[w])
        sz[v] = s
    h_ps.append(tmp_ps[0])

    ans = [-1]*N
    ph = Prop()
    for path in h_ps:
        h = -1
        for v in path:
            p = prt[v]

            for w in G[v]:
                if w == p or w == h:
                    continue
                for c in order[pn[w]:pn[w] + sz[w]]:
                    ph.add(c)
            ph.add(v)
            ans[v] = ph.get(v)
            h = v

        # 削除操作で初期化する
        for c in order[pn[v]:pn[v] + sz[v]]:
            ph.remove(c)
        # 一括で初期化する場合 (更新した箇所のみ更新する)
        # ph.reset()
    return ans

Verified

  • AOJ: "2995 - Colorful Tree": source (Python3, 2.74sec)

  • Codeforces: "600E: Lomsat gelral": source (Python3, 1559ms)

  • Codeforces: "246E: Blood Cousins Return": source (Python3, 2870ms)

  • Codeforces: "375D: Tree and Queries": source (PyPy3, 920ms)

参考

戻る