全方位木DP (Re-Rooting)
(Graph/Tree/rerooting.py)

• View this file on GitHub
• Last update: 2021-01-14 15:36:57+09:00

使い方

rerooting(n, edges, unit, merge, addnode) -> List[Any]

• n 頂点の木（もしくは森）に対して、頂点属性の全方位木DPを行った結果を返す。辺は隣接リストとして edges で渡す。計算量 $O(n)$

• merge 関数は子の部分木同士の演算を表し、unit は演算の単位元である。これはモノイドとなる。

• addnode 関数は子の部分木と自身との演算を表す。
  

• 辺属性の全方位木DPをしたい場合は、あらかじめ 辺情報を頂点情報へと変換 しておけばよい。

参考

【全方位木DP】明日使える便利な木構造のアルゴリズム

Verified with

• TestCase/AOJ/GRL_5_A.test.py
• TestCase/AOJ/GRL_5_B.test.py
• TestCase/yukicoder/yuki0922.HLDecomposition.test.py
• TestCase/yukicoder/yuki0922.test.py

Code

def rerooting(n, edges, unit, merge, addnode):
    tree = [[] for i in range(n)]
    idxs = [[] for i in range(n)]
    for u, v in edges:
        idxs[u].append(len(tree[v]))
        idxs[v].append(len(tree[u]))
        tree[u].append(v)
        tree[v].append(u)
    sub = [[unit] * len(tree[v]) for v in range(n)]
    noderes = [unit] * n

    # topological sort
    tp_order = []
    par = [-1] * n
    for root in range(n):
        if par[root] != -1:
            continue
        stack = [root]
        while stack:
            v = stack.pop()
            tp_order.append(v)
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                par[nxt_v] = v
                stack.append(nxt_v)

    # tree DP
    for v in reversed(tp_order[1:]):
        res = unit
        par_idx = -1
        for idx, nxt_v in enumerate(tree[v]):
            if nxt_v == par[v]:
                par_idx = idx
                continue
            res = merge(res, sub[v][idx])
        if par_idx != -1:
            sub[par[v]][idxs[v][par_idx]] = addnode(res, v)

    # rerooting DP
    for v in tp_order:
        acc_back = [unit] * len(tree[v])
        for i in reversed(range(1, len(acc_back))):
            acc_back[i - 1] = merge(sub[v][i], acc_back[i])
        acc_front = unit
        for idx, nxt_v in enumerate(tree[v]):
            res = addnode(merge(acc_front, acc_back[idx]), v)
            sub[nxt_v][idxs[v][idx]] = res
            acc_front = merge(acc_front, sub[v][idx])
        noderes[v] = addnode(acc_front, v)
    return noderes

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page