~ Esoteria Algorithm in Reverse Observatory

JSK31435 | 敌对势力

Portal

本 blog 最水的文章之一。题面藥丸。我就什么话也不说。

倍增 LCA

Prologue

给定一棵有根树,若节点 zz 既是节点 xx 的祖先,也是节点 yy 的祖先,则称 zzx,yx,y 的公共祖先。在 x,yx,y 的所有公共祖先中,深度最大的一个称为 x,yx,y 的最近公共祖先,记为 LCA(x,y)\text{LCA} (x,y)