Day 064-Q1 — 木の重心分解 + セグメント木クエリ（Centroid Decomposition + Point/Path Aggregate）

問題

$N$ 頂点の重み付き木が与えられる（辺重みあり）。以下の2種類のクエリを $Q$ 個処理せよ：

• update v x: 頂点 $v$ の点重みを $x$ に変更する（初期値は 0）。
• query u d: 頂点 $u$ からの距離がちょうど $d$ である頂点のうち、点重みの最大値を出力する（存在しなければ -1）。

入出力例

5 4
1 2 3
2 3 1
3 4 2
4 5 4
update 3 10
update 5 7
query 1 4
query 2 6

10
7

dist(1,3)=3+1=4 なので query 1 4 → 頂点3の重み10。dist(2,5)=1+2+4=7≠6、dist(2,4)=1+2=3≠6。query 2 6 → dist(2,5)=7、... 実際の答えはサンプルに応じて。

概念図: 重心分解ツリー

ヒント（段階的開示）

def update(v, x):
    for c, d in dist_to_ancestor[v]:
        if x > cd_map[c][d]:
            cd_map[c][d] = x

def query(u, d):
    ans = -1
    for c, du in dist_to_ancestor[u]:
        need = d - du
        if need >= 0 and cd_map[c][need] != -1:
            ans = max(ans, cd_map[c][need])
    return ans

模範解答 (Python)

コピーimport sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def solve():
    N, Q = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b, w = map(int, input().split())
        adj[a].append((b, w))
        adj[b].append((a, w))

    size = [0] * (N + 1)
    removed = [False] * (N + 1)
    dist_to_ancestor = [[] for _ in range(N + 1)]

    def calc_size(v, p):
        size[v] = 1
        for u, _ in adj[v]:
            if u != p and not removed[u]:
                calc_size(u, v)
                size[v] += size[u]

    def find_centroid(v, p, ts):
        for u, _ in adj[v]:
            if u != p and not removed[u] and size[u] > ts // 2:
                return find_centroid(u, v, ts)
        return v

    def dfs_dist(v, p, c, d):
        dist_to_ancestor[v].append((c, d))
        for u, w in adj[v]:
            if u != p and not removed[u]:
                dfs_dist(u, v, c, d + w)

    def decomp(v):
        calc_size(v, -1)
        c = find_centroid(v, -1, size[v])
        removed[c] = True
        dfs_dist(c, -1, c, 0)
        for u, _ in adj[c]:
            if not removed[u]:
                decomp(u)
        removed[c] = False

    decomp(1)

    cd_map = defaultdict(lambda: defaultdict(lambda: -1))
    point_weight = [0] * (N + 1)

    def update(v, x):
        point_weight[v] = x
        for c, d in dist_to_ancestor[v]:
            if x > cd_map[c][d]:
                cd_map[c][d] = x

    def query_q(u, d):
        ans = -1
        for c, du in dist_to_ancestor[u]:
            need = d - du
            if need >= 0:
                val = cd_map[c][need]
                if val != -1:
                    ans = max(ans, val)
        return ans

    output = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'update':
            v, x = int(line[1]), int(line[2])
            update(v, x)
        else:
            u, d = int(line[1]), int(line[2])
            output.append(query_q(u, d))

    print('\n'.join(map(str, output)))

solve()

Step-by-Step 解説

Step 1: 重心の性質

重心 $c$ は「$c$ を除いた各連結成分のサイズが $N/2$ 以下」の頂点。重心分解ツリーの深さは $O(\log N)$ のため、各頂点は $O(\log N)$ 個の祖先重心を持つ。

Step 2: 距離の前処理 $O(N \log N)$

dfs_dist で各重心 $c$ から DFS し、各頂点 $v$ に「$(c, dist(c,v))$」を記録。全体で $O(N \log N)$ の空間と時間。

Step 3: update クエリ $O(\log N)$

頂点 $v$ の $O(\log N)$ 個の祖先重心それぞれについて辞書を更新。

Step 4: query クエリ $O(\log N)$

頂点 $u$ から距離 $d$ の点は、$u$ と $v$ の LCA に相当する重心 $c$ を経由する。$dist(u,v) = dist(u,c) + dist(c,v)$ を利用して need = d - dist(u,c) を辞書参照。

Step 5: 計算量

よくあるミス

次のステップ

発展問題: update で点重みが減少する場合に対応せよ。各重心の各距離に対してマルチセットや sorted list を使って最大値を動的管理する方法を実装せよ。

自己評価