ツリーの重軽分解：長子優先によるパス操作の高速化
セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。
木上のパスを線形構造に変換するアイデア
木は分岐構造を持つため ...
8月19日 04:01 投稿
樹における最近共通祖先の効率的計算手法
木構造上の2頂点間の最近共通祖先（Lowest Common Ancestor, LCA）を高速に求めるには、複数のアルゴリズムが存在します。本稿では、倍増法、オイラー巡回＋RMQ、および木の重軽分解（Heavy-Light Decomposition）の3つの代表的手法について、それぞれの設計思想・実装構造・計算量特性を解説します。
倍増法によるLCAクエリ
各頂点から根方向へ2kステップ先の祖先とその ...
8月5日 03:47 投稿
NOIP2013 提高組: 貨物輸送経路の最大最小辺問題
問題概要
無向グラフが与えられ、各辺には重みが付与されています。クエリでは2頂点間の経路における最小辺重みの最大値を求める必要があります。グラフは非連結の可能性があり、効率的な解法が求められます。
解法アプローチ
最適経路は最大ボトルネック生成木(MBST)上に存在します。MBSTはKruskal法を重み降順で適用して構築します。非連結グラフ対応のため、Union-Find ...
7月1日 17:43 投稿
青染之心の解法：重軽分解とブロック分割法
解法1: 重軽分解によるアプローチ
オフライン処理可能な問題特性を利用し、操作履歴から木構造を構築する。各ノードの解は根からそのノードまでのアイテムを用いた完全ナップサック問題と等価である。
深さ優先探索(DFS)実行時、再帰スタックにナップサック状態を保持する。空間計算量を削減するため、重軽分解(Heavy-Light Decomposition)を適用する。具体的には:
各ノー ...
5月31日 09:21 投稿