倍增专题本蒟蒻只会个倍增lca，实在太菜了。
稍微灵活一下的倍增就不会了，所以开一个倍增专题，先把倍增练熟


1.跑路
由每次走 2k米很容易想到倍增。
map[k][i][j]表示从i走2k米能否走

[luoguP2680] 运输计划（lca + 二分 + 差分）传送门

暴力做法 50 ~ 60
枚举删边，求最大路径长度的最小值。
其中最大路径长度运用到了lca

我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。
先把

[luoguP3258] [JLOI2014]松鼠的新家（lca + 树上差分）传送门

需要把一条路径上除了终点外的所有数都 + 1，
比如，给路径 s t 上的权值 + 1，可以先求 x = lca(s，t)
类似数列上差分的思路，可以给 s 和 f[t] 的权值 + 1，给 x 和 f[x]

[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）传送门

水题。
直接倍增求lca。
x到y的距离为dis[x] + dis[y] 2 * dis[lca(x, y)]

——代码


1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4

[bzoj1787][Ahoi2008]Meet 紧急集合（lca）传送门

可以看出，三个点两两之间的lca会有一对相同，而另一个lca就是聚集点。
然后搞搞就可以求出距离了。

——代码


1 #include <cstdio>
2 #include <cstring>
3 #in

lca最近公共祖先（模板）洛谷上的lca模板题——传送门
1.tarjan求lca
学了求lca的tarjan算法（离线），在洛谷上做模板题，结果后三个点超时。
又把询问改成链式前向星，才ok。
这个博客，tarjan分析的很详细。

NOIP2013D1T3货车运输（最大生成树+倍增lca）传送门
这道题，先用kruskal求一遍图中的最大生成树。
然后，倍增求lca，求lca的同时求出边权的最小值。


#include <cstring>
#include <cstdio>
#include <algorithm>

int n,