运用树上倍增法可以高效率地求出两点x,y的公共祖先LCA
我们设f[x][k]表示x的2k辈祖先
f[x][0]为x的父节点
因为从x向根节点走2k 可以看成从x走2k-1步 再走2k-1步
所以对于1≤k≤logn 有f[x][k]=f[f[x][k-1]][k-1] （类似二分思想）
因此我们可以对树进行遍历后得到所有f[x][0] 再计算出f数组的所有值
设dep[x]为x的深度 设dep[x]≥dep[y]（否则 可以交换x和y）
使用二进制拆分 把x和y调整到同一深度
若此时
原文：https://www.cnblogs.com/BrokenString/p/9775540.html