[luoguP3302] [SDOI2013]森林（主席树 + 启发式合并 + lca）传送门显然树上第k大直接主席树如果连边的话，我们重构小的那一棵，连到另一棵上。说起来简单，调了我一晚上。总的来说3个错误：1.离散化写错位置写到了后面2."="写成了"=="3.加双

[POJ3728]The merchant（tanrjan_lca + DP）传送门

比着题解写还错。。。
查了两个小时没查出来，心态爆炸啊
以后再查

——代码（WA）


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

[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,