LCA的多种求法（超详细！！！）

倍增求LCA

(1)树上倍增法 预处理

设f[x,k]表示x的2^k辈祖先,即从x向根节点走2^k步到达的节点。特别地,若该节点不存在,则令f[x,k]=0。f[x,0]就是x的父节点。可以得出设f[x,k]表示x的2^k辈祖先,即从x向根节