2017-09-08から1日間の記事一覧

Euler Tour

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…