一.倍增的思想
倍增的思想~啾咪！
震惊！一只小兔子竟然干出这样的事情......
https://blog.csdn.net/dong_qian/article/details/81702697
二.倍增的应用——lca
1.资本：f [ x ] [ i ]：x向上条2^i步的节点。
dep [ x ]：x点的深度。
2.步骤：分两个函数。第一个是预处理 f 数组。第二个是正儿八经求lca。
求lca时，首先让a、b跳到同一层。此时若a==b，则他们正处于他们lca的位置，return。
让a、b同时往上跳，若他们倍增后的点不同，说明他们还没有到达lca，继续跳。最后输出f [ x ] [ 0 ]。
3.代码：
part one
void deal(int son,int fa) { dep[son]=dep[fa]+1; f[son][0]=fa; for(int i=1;i<20;i++) { f[son][i]=f[f[son][i-1]][i-1]; } for(int i=head[son];i;i=edge[i].next) { int sson=edge[i].to; if(sson!=fa)deal(sson,son); } }
part two
int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=19;i>=0;i--) { if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; } for(int i=20;i>=0;i++) { if(f[x][i]!=f[y][i]) { y=f[y][i]; x=f[x][i]; } } return f[x][0]; }
原文：https://www.cnblogs.com/SUMMER20020929/p/10559636.html