math314のブログ

最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。 アルゴリズム edgeを"Heavy"と"Light"に分けて "Heavy"edgeで繋がれた頂点を一つにまとめる の2段構成。 ここに書いてあるedgeの分け方は元のHeavy Light Decompositionと違うかも *1:[要出典]