HL分解

各頂点から部分木が最も大きい子への辺を heavy edge とし、heavy edge でつながった頂点が連続するように、DFS の行きがけ順で頂点を並べます。どのパスも $O(\log N)$ 本の heavy path にしかまたがらないので、パス上の頂点は列の $O(\log N)$ 個の区間に分かれます。部分木は 1 つの区間になります。再帰は使いません。

• HLD(g, root): 木の隣接リスト g[v] = [to, ...] と根から前計算。 $O(N)$
• pos[v], order: 列での $v$ の位置と、位置の順に並べた頂点のリスト（order[pos[v]] == v）
• path(u, v, edge=False): $u$ と $v$ を結ぶパス上の頂点の位置を、半開区間 (l, r) のリストで返す（区間の順番はばらばら）。edge=True にすると LCA を除く。 $O(\log N)$
• subtree(v): $v$ の部分木の頂点の位置を表す半開区間 (l, r)。 $O(1)$
• lca(u, v), dist(u, v): 最小共通祖先と距離（辺の本数）。 $O(\log N)$
• kth_ancestor(v, k): $v$ の $k$ 個上の祖先（存在しなければ $-1$）。 $O(\log N)$
• jump(u, v, k): $u$ から $v$ へのパス上で、 $u$ から $k$ 番目（0-indexed）の頂点（ $k$ が $u$ と $v$ の距離より大きければ $-1$）。 $O(\log N)$
• par[v], depth[v], size[v], head[v]: 親（根は $-1$）、深さ、部分木の頂点数、 $v$ を含む heavy path のうち最も根に近い頂点

辺に値があるときは、辺 $(\mathrm{par}[v], v)$ の値を位置 pos[v] に置き、edge=True で区間を求めます。path が返す区間は順番がばらばらなので、パス上の値をまとめる演算は可換なもの（和・最大値・xor など）に限ります。

例（頂点の値の更新と、パス上の頂点の値の和。ACL の Fenwick Tree を使う）:

from atcoder.fenwicktree import FenwickTree

hld = HLD(g)
bit = FenwickTree(n)
for i in range(n):
    bit.add(hld.pos[i], a[i])
# 頂点 v の値に x を足す
bit.add(hld.pos[v], x)
# u と v を結ぶパス上の頂点の値の和
s = sum(bit.sum(l, r) for l, r in hld.path(u, v))

コード

class HLD:
    def __init__(self, g, root=0):
        n = len(g)
        par = [-1] * n
        depth = [0] * n
        bfs = [root]
        for v in bfs:
            for to in g[v]:
                if to != par[v]:
                    par[to] = v
                    depth[to] = depth[v] + 1
                    bfs.append(to)
        size = [1] * n
        for v in reversed(bfs[1:]):
            size[par[v]] += size[v]
        heavy = [-1] * n  # 部分木が最も大きい子
        for v in bfs:
            for to in g[v]:
                if to != par[v] and (heavy[v] == -1 or size[to] > size[heavy[v]]):
                    heavy[v] = to
        head = [root] * n  # v を含む heavy path の、根に最も近い頂点
        pos = [0] * n      # 列での v の位置
        order = []         # order[pos[v]] = v
        st = [root]
        while st:
            v = st.pop()
            pos[v] = len(order)
            order.append(v)
            for to in g[v]:
                if to != par[v] and to != heavy[v]:
                    head[to] = to
                    st.append(to)
            if heavy[v] != -1:
                head[heavy[v]] = head[v]
                st.append(heavy[v])
        self.par = par
        self.depth = depth
        self.size = size
        self.head = head
        self.pos = pos
        self.order = order

    def lca(self, u, v):
        pos, head = self.pos, self.head
        while True:
            if pos[u] > pos[v]:
                u, v = v, u
            if head[u] == head[v]:
                return u
            v = self.par[head[v]]

    def dist(self, u, v):
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

    def kth_ancestor(self, v, k):
        # v の k 個上の祖先（存在しなければ -1）
        if k > self.depth[v]:
            return -1
        while True:
            h = self.head[v]
            if self.pos[v] - self.pos[h] >= k:
                return self.order[self.pos[v] - k]
            k -= self.pos[v] - self.pos[h] + 1
            v = self.par[h]

    def jump(self, u, v, k):
        # u から v へのパスで、u から k 番目（0-indexed）の頂点（k が距離より大きければ -1）
        w = self.lca(u, v)
        du = self.depth[u] - self.depth[w]
        dv = self.depth[v] - self.depth[w]
        if k <= du:
            return self.kth_ancestor(u, k)
        if k <= du + dv:
            return self.kth_ancestor(v, du + dv - k)
        return -1

    def path(self, u, v, edge=False):
        # u-v パス上の頂点の位置を、半開区間 [l, r) のリストで返す（区間の順番はばらばら）
        # edge=True なら LCA を除く（辺 (par[x], x) を位置 pos[x] に置いたときの、パス上の辺）
        pos, head = self.pos, self.head
        res = []
        while True:
            if pos[u] > pos[v]:
                u, v = v, u
            if head[u] == head[v]:
                l = pos[u] + 1 if edge else pos[u]
                if l <= pos[v]:
                    res.append((l, pos[v] + 1))
                return res
            res.append((pos[head[v]], pos[v] + 1))
            v = self.par[head[v]]

    def subtree(self, v):
        # v の部分木の頂点の位置の半開区間 [l, r)
        return self.pos[v], self.pos[v] + self.size[v]