木の連鎖分解（ヘビーライト分解）のまとめ

• 基本概念
• • 基本的な考え方
    • 実装手順
    • • ステップ1: 重い子、重い連鎖
        • ステップ2: dfn順序
        • ステップ3: 時間計算量の分析
    • コード実装
    • • 重い子の検出
        • 連鎖分解
        • 各種操作
        • • LCAの計算：
            • パス更新：
            • パスクエリ：
• 推奨問題

基本概念

基本的な考え方

\qquad 木の連鎖分解、名前の通り、木データ構造に適用されるアルゴリズムです。一般的に動的なパス情報や部分木情報の維持に使用され、例えばパスの重み値の更新、パスクエリによる重み和（最大値）の取得、部分木クエリによる重み和（最大値）の取得などの問題に対応します。木の連鎖分解は木を複数の連鎖に分割し、dfn順序上にセグメントツリーを実装することで動的な区間情報の維持を実現します。

実装手順

ステップ1: 重い子、重い連鎖

\qquad タイトルを振り返ります：木の連鎖分解（ヘビーライト分解）、なぜ括弧内に「ヘビーライト分解」と追加されるのでしょうか？

木の連鎖分解（木剖/連鎖剖）には複数の形式があり、ヘビーライト分解、長連鎖分解、Link/cutツリーで使用される分解（時々「実連鎖分解」と呼ばれます）などがあります。ほとんどの場合（特に指定がない場合）、「木の連鎖分解」は「ヘビーライト分解」を指します。—— oi-wikiより

\qquad ここで言うヘビーライト分解とは何でしょうか？その前に、まず重い子とは何かを理解しましょう。

\qquad 「重い」子、なぜ「重い」と言うのでしょうか？木において、どのような情報が「軽重」という表現に適切で、的確なのでしょうか？もちろんsize（部分木の大きさ）です！形式的に重い子を定義してみましょう：点xの重い子をson_x、点xの子たちをto_x、点xを根とする部分木の大きさをsze_xとすると、son_x = max_{u∈to_x} sze_u となります。言い換えると、重い子はすべての子ノードの中で最大の部分木サイズを持つものです。残りの子ノードを軽い子と定義し、点xからson_xへの辺を重い辺、残りの辺を軽い辺とします；同時に、複数の（0個でも可）重い辺が首尾つながって形成される連鎖を重い連鎖と呼びます。そうすると、木全体を複数の重い連鎖に分割でき、すべての点は必ず一つの重い連鎖に含まれます。これは重い連鎖を使って木を完全に分割できることを意味します。

ステップ2：dfn順序

\qquad 木の連鎖分解の説明で、dfn順序とセグメントツリーを組み合わせて部分木の更新、クエリ、パスの更新、クエリを実現すると述べました。部分木の操作については、部分木内の点のdfn順序は常に連続していることが分かっており、部分木の操作は簡単に実現できます。ではパス操作はどうすれば良いのでしょうか？

\qquad 上記で重い連鎖が木を完全に分割できると述べました。そこで、dfs時にまず重い子を再帰的に処理し、次に軽い子を再帰的に処理するようにすれば、部分木内のdfn順序の連続性だけでなく、一つの重い連鎖上の点のdfn順序も連続していることが保証されます。この重要な性質により、重い連鎖の更新が容易になります。この点を考えると、パス更新は簡単になります：あるパスが点xから点yであるとすると、このパスをlcaからxへのパスとlcaからyへのパスの2つに分割し、それぞれxとyからlcaに向かって重い連鎖をジャンプさせます。一つの重い連鎖については、まずこの連鎖の片端にジャンプしてΘ(log n)時間で更新し、直接もう片端にジャンプして、他の重い連鎖へと上へジャンプし、この操作を繰り返すだけです。これがヘビーライト分解操作の全体プロセスです。

ステップ3：時間計算量の分析

\qquad 上記の操作は非常に直接的に見えますが、このプロセスの時間計算量を分析してみましょう。まず、このプロセスの時間計算量はジャンプした重い連鎖の数に密接に関連しており、その長さにはあまり関係ありません。2つの重い連鎖は一つの軽い辺で分断されることが分かります。したがって、このプロセスで何個の軽い辺を通過するかだけを分析すれば十分です。これがなぜ重い子を定義する必要があったかに関係します。

\qquad 重い子の部分木サイズはすべての子の中で最大ですが、その大きさの範囲を特定することはできません。ある連鎖では、重い子の部分木サイズはΘ(n)レベルに達する可能性がありますが、菊図形ではこのサイズは1しかないかもしれません。しかし、軽い子の部分木サイズの範囲は特定できます。軽い子の部分木サイズは必ずsze_x/2以下です。これは背理法で簡単に証明できます。さらに分析すると、一つの軽い辺を通過するごとに部分木サイズは少なくとも2で割られるため、最大でΘ(log n)個の軽い辺しか通過しないことが分かります。つまり、連鎖をジャンプする回数もΘ(log n)レベルであり、セグメントツリーと組み合わせることで全体の時間計算量はΘ(n log² n)となり、部分木操作やパス操作の問題を簡単に解決できます。

コード実装

重い子の検出

void heavy_child_dfs(int node, int parent) {
   subtree_size[node] = 1, depth[node] = depth[parent] + 1, parent_node[node] = parent;
   for(int i = head[node]; i; i = edge[i].next) {
       int neighbor = edge[i].target;
       if(neighbor == parent) continue;
       heavy_child_dfs(neighbor, node);
       subtree_size[node] += subtree_size[neighbor];
       if(subtree_size[neighbor] > subtree_size[heavy_child[node]]) 
           heavy_child[node] = neighbor;
   }
}

連鎖分解

\qquad これは木の連鎖分解で最も重要なdfsです。

void decompose(int node, int parent, int chain_id) {
   chain[node] = chain_id;
   dfs_order[node] = ++ order_counter;
   ordered_nodes[order_counter] = node;
   if(heavy_child[node]) 
       decompose(heavy_child[node], node, chain_id);
   for(int i = head[node]; i; i = edge[i].next) {
       int neighbor = edge[i].target;
       if(neighbor == parent || neighbor == heavy_child[node]) continue;
       decompose(neighbor, node, neighbor);
   }
}

各種操作

LCAの計算：

int lowest_common_ancestor(int x, int y) {
   while(chain[x] != chain[y]) {
       if(depth[chain[x]] > depth[chain[y]]) 
           x = parent_node[chain[x]];
       else 
           y = parent_node[chain[y]];
   }
   return depth[x] > depth[y] ? y : x;
}

パス更新：

void path_update(int x, int y, int value) {
   for(; chain[x] != chain[y]; x = parent_node[chain[x]]) 
       segment_tree_update(1, dfs_order[chain[x]], dfs_order[x], value);
   segment_tree_update(1, dfs_order[y] + 1, dfs_order[x], value);
}

// main 関数内
int Lca = lowest_common_ancestor(u, v);
path_update(u, Lca, w);
path_update(v, Lca, w); // パスを2つに分割してそれぞれ更新

パスクエリ：

int path_query(int x, int y) {
   int max_val = 0;
   for(; chain[x] != chain[y]; x = parent_node[chain[x]]) 
       max_val = max(max_val, segment_tree_query(1, dfs_order[chain[x]], dfs_order[x]));
   max_val = max(max_val, segment_tree_query(1, dfs_order[y] + 1, dfs_order[x]));
   return max_val;
}

// main 関数内
int Lca = lowest_common_ancestor(u, v);
printf("%d\n", max(path_query(u, Lca), path_query(v, Lca)));

推奨問題

\qquad [ZJOI2008] 木の統計 - 基本的な問題

\qquad [HAOI2015] 木上の操作 - 基本的な問題

\qquad [NOI2015] ソフトウェアパッケージマネージャ - 基本的な問題

\qquad 月下「毛景木」 - 基本的な問題ですが、辺の重みを点の重みに変換する必要があり、少し注意が必要

\qquad QTREE - Query on a tree - 辺の重みを点の重みに変換

\qquad [国家トレーニングチーム] 旅行 - 木の連鎖分解の基本的な問題、主にセグメントツリーの操作を試す

\qquad [SDOI2011] 塗りつぶし - 色のセグメントを処理する際に少し注意が必要な点がある