Static Top Tree
HL 分解 と同じく、各頂点から部分木が最も大きい子(heavy child)への辺で、木を heavy path に分けます。heavy path 上の頂点は上から順に compress でつなぎ、各頂点の light な子の部分木は rake でまとめます。どちらも部分木の大きさで釣り合うように二分木にするので、全体の深さが $O(\log N)$ になります。頂点 $v$ のデータを変えたら、 $v$ から根までの $O(\log N)$ 個のノードだけを計算し直します。前計算も更新も再帰は使いません。
まとめる値(クラスタ)は 2 種類です。パスクラスタは、heavy path の一続きの部分と、その頂点たちから下がる light な子の部分木をまとめたもので、下の端の頂点の heavy child から下は含みません(穴として残します)。点クラスタは、1 つの頂点の light な子いくつかの部分木を、その頂点への辺ごとまとめたものです。問題ごとに次の 5 つの関数を決めて渡します。値にはタプルのような、書き換えないものを使います。
vertex(v): light な子がない頂点 $v$ だけのパスクラスタcompress(p, c): 上のパスクラスタ $p$ の穴に、下のパスクラスタ $c$ をつないだパスクラスタ(結合的であること)rake(x, y): 同じ頂点の下にある 2 つの点クラスタをまとめた点クラスタ(結合的かつ可換であること)add_edge(p): heavy path 全体のパスクラスタ $p$ に、一番上の頂点から親への辺を加えた点クラスタadd_vertex(x, v): 頂点 $v$ の light な子の部分木をすべてまとめた点クラスタ $x$ に、 $v$ を加えたパスクラスタ
heavy path の一番下はいつも葉なので、add_edge と get で使うパスクラスタの穴は空です。
StaticTopTree(n, edges, root, vertex, compress, rake, add_edge, add_vertex): 頂点数 $n$、木の辺のリストedges = [(u, v), ...]、根rootと上の 5 つの関数から作り、すべてのクラスタを計算する。 $O(N \log N)$update(v): 頂点 $v$ のデータ(vertex(v)やadd_vertex(x, v)が読む値)を変えたあとに呼び、 $v$ から根までのクラスタを計算し直す。 $O(\log N)$(5 つの関数が $O(1)$ のとき)get(): 木全体のパスクラスタ(根を含む heavy path 全体)。 $O(1)$
辺に値があるときは、辺 $(\mathrm{par}(v), v)$ の値を子の側の頂点 $v$ のデータとして、vertex(v) と add_vertex(x, v) で $v$ と一緒に加えます(値を変えたら update(v) を呼ぶ)。
例(ABC 351 G。頂点 $v$ の値 $f(v)$ を、 $v$ が葉なら $a_v$、葉でなければ $a_v$ に子 $c$ の $f(c)$ の積を足したものとする。 $a_v$ を変えるたびに $f(\mathrm{root}) \bmod 998244353$ を求める):
パスクラスタを、穴の値(下の端の頂点の heavy child $h$ の $f(h)$)を $x$ として、上の端の頂点の $f$ の値を返す 1 次関数 $x \mapsto s x + t$ で表し、タプル (s, t) で持ちます。頂点 $v$ の light な子の $f$ の積を $m$ (light な子がなければ $m = 1$)とすると $f(v) = m x + a_v$ なので、 $v$ だけのパスクラスタは (m, a[v]) です。compress は 1 次関数の合成、点クラスタは light な子の $f$ の積で、rake は掛け算です。葉には heavy child がありませんが、 $x = 0$ とすると $f(v) = a_v$ となって葉の式と一致します。なので add_edge(p) と答えは $x = 0$ のときの値 $t$ です。
MOD = 998244353
# パスクラスタ (s, t): 穴の値 x から、上の端の頂点の値 s x + t を返す 1 次関数
def vertex(v):
return (1, a[v])
def compress(p, c):
# x を c に通してから p に通す
return (p[0] * c[0] % MOD, (p[0] * c[1] + p[1]) % MOD)
def rake(x, y):
return x * y % MOD
def add_edge(p):
return p[1] # 穴が空(x = 0)のときの値
def add_vertex(m, v):
return (m, a[v]) # m は light な子の f の積
edges = [(p[i], i) for i in range(1, n)] # p[i] は頂点 i の親(根は 0)
stt = StaticTopTree(n, edges, 0, vertex, compress, rake, add_edge, add_vertex)
for v, x in queries:
a[v] = x
stt.update(v)
print(stt.get()[1])
コード
from bisect import bisect_left
class StaticTopTree:
# 根付き木の DP を、頂点のデータを変えるたびに O(log N) で計算し直す
# heavy path を compress で、light な子の部分木を rake でまとめた、深さ O(log N) の二分木を作る
def __init__(self, n, edges, root, vertex, compress, rake, add_edge, add_vertex):
self.vertex = vertex
self.compress = compress
self.rake = rake
self.add_edge = add_edge
self.add_vertex = add_vertex
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
par = [-1] * n
order = [root]
for v in order:
for to in g[v]:
if to != par[v]:
par[to] = v
order.append(to)
size = [1] * n
for v in reversed(order):
if v != root:
size[par[v]] += size[v]
heavy = [-1] * n # 部分木が最も大きい子
for v in order:
p = par[v]
if p != -1 and (heavy[p] == -1 or size[v] > size[heavy[p]]):
heavy[p] = v
# ノード x の子 L[x], R[x]、親 P[x]、種類 T[x]、クラスタの値 val[x]
# ノード v (< n) は頂点 v(T = 0: vertex, 4: add_vertex)
# n 以降は T = 1: compress, 2: rake, 3: add_edge
self.L = [-1] * n
self.R = [-1] * n
self.P = [-1] * n
self.T = [0] * n
self.val = [None] * n
edge_node = [-1] * n # light な子 c の部分木を表す点クラスタ(add_edge)のノード
# 下の heavy path から順に作る(light な子の部分木は先にできている)
for t in reversed(order):
if t != root and heavy[par[t]] == t:
continue
path = []
ws = []
v = t
while v != -1:
cs = [c for c in g[v] if c != par[v] and c != heavy[v]]
if cs:
x = self._merge([edge_node[c] for c in cs], [size[c] for c in cs], 2)
self.L[v] = x
self.P[x] = v
self.T[v] = 4
self.val[v] = add_vertex(self.val[x], v)
else:
self.val[v] = vertex(v)
path.append(v)
h = heavy[v]
ws.append(size[v] - size[h] if h != -1 else 1)
v = h
x = self._merge(path, ws, 1)
if t == root:
self.root = x
else:
y = self._new(3)
self.L[y] = x
self.P[x] = y
self.val[y] = add_edge(self.val[x])
edge_node[t] = y
def _new(self, t):
self.L.append(-1)
self.R.append(-1)
self.P.append(-1)
self.T.append(t)
self.val.append(None)
return len(self.L) - 1
def _merge(self, xs, ws, t):
# ノード xs をこの順に、重み ws で釣り合うように種類 t のノードでまとめ、根を返す
k = len(xs)
if k == 1:
return xs[0]
L, R, P = self.L, self.R, self.P
pre = [0] * (k + 1)
for i in range(k):
pre[i + 1] = pre[i] + ws[i]
q = [pre[i] + pre[i + 1] for i in range(k)]
start = self._new(t)
st = [(0, k, start)]
while st:
lo, hi, x = st.pop()
# [lo, m) の重みがおよそ半分になる m で分ける(lo < m < hi)
m = bisect_left(q, pre[lo] + pre[hi], lo + 1, hi - 1)
if m - lo == 1:
y = xs[lo]
else:
y = self._new(t)
st.append((lo, m, y))
L[x] = y
P[y] = x
if hi - m == 1:
y = xs[m]
else:
y = self._new(t)
st.append((m, hi, y))
R[x] = y
P[y] = x
# 子は親より後に作ったので、後ろから値を計算する
f = self.compress if t == 1 else self.rake
val = self.val
for x in range(len(L) - 1, start - 1, -1):
val[x] = f(val[L[x]], val[R[x]])
return start
def update(self, v):
# 頂点 v のデータを変えたあとに呼ぶ(v から根までのノードを計算し直す)
L, R, P, T, val = self.L, self.R, self.P, self.T, self.val
compress, rake, add_edge, add_vertex = self.compress, self.rake, self.add_edge, self.add_vertex
if T[v] == 0:
val[v] = self.vertex(v)
else:
val[v] = add_vertex(val[L[v]], v)
x = P[v]
while x != -1:
t = T[x]
if t == 1:
val[x] = compress(val[L[x]], val[R[x]])
elif t == 2:
val[x] = rake(val[L[x]], val[R[x]])
elif t == 3:
val[x] = add_edge(val[L[x]])
else:
val[x] = add_vertex(val[L[x]], x)
x = P[x]
def get(self):
# 木全体のパスクラスタ(根を含む heavy path 全体)
return self.val[self.root]