オイラーツアー

頂点を DFS の行きがけ順に並べると、どの頂点の部分木も連続した区間になります。BIT やセグ木と組み合わせると、部分木やパスに関するクエリを列のクエリとして処理できます。再帰は使いません。

• EulerTour(g, root): 木の隣接リスト g[v] = [to, ...] と根から前計算。 $O(N)$
• order: 行きがけ順に並べた頂点のリスト（order[tin[v]] == v）
• tin[v], tout[v]: $v$ の部分木の頂点は、order のうち添字が tin[v] 以上 tout[v] 未満の部分
• par[v], depth[v]: 親（根は $-1$）と深さ
• is_ancestor(u, v): $u$ が $v$ の祖先か（ $u = v$ のときも True）。 $O(1)$

使い方の例:

• 部分木の和: 頂点 $v$ の値を位置 tin[v] に置き、区間 [tin[v], tout[v]) の和を取る
• 根からのパスの和: 頂点 $u$ の値 $x$ を「位置 tin[u] に $+x$、位置 tout[u] に $-x$」として置くと、根から $v$ までのパス上の和は位置 tin[v] までの累積和になる

コード

class EulerTour:
    def __init__(self, g, root=0):
        n = len(g)
        par = [-1] * n
        depth = [0] * n
        tin = [0] * n
        tout = [0] * n
        order = []
        st = [root]
        while st:
            v = st.pop()
            if v >= 0:
                tin[v] = len(order)
                order.append(v)
                st.append(~v)
                for to in reversed(g[v]):
                    if to != par[v]:
                        par[to] = v
                        depth[to] = depth[v] + 1
                        st.append(to)
            else:
                tout[~v] = len(order)
        self.par = par
        self.depth = depth
        self.tin = tin
        self.tout = tout
        self.order = order

    def is_ancestor(self, u, v):
        # u が v の祖先か（u == v も含む）
        return self.tin[u] <= self.tin[v] < self.tout[u]