lca文章列表
[luoguP3302] [SDOI2013]森林（主席树 + 启发式合并 + lca）
传送门 显然树上第k大直接主席树 如果连边的话，我们重构小的那一棵，连到另一棵上。 说起来简单，调了我一晚上。 总的来说3个错误： 1.离散化写错位置写到了后面 2."="写成了"==" 3.加双向边...主席树,lca,启发式合并
[POJ3728]The merchant（tanrjan_lca + DP）
传送门 比着题解写还错。。。 查了两个小时没查出来，心态爆炸啊 以后再查 ——代码（WA） 1 #include cstdio 2 #include cstring 3 #include iostre...DP,lca,tarjan
[luoguP2680] 运输计划（lca + 二分 + 差分）
传送门 暴力做法 50 ~ 60 枚举删边，求最大路径长度的最小值。 其中最大路径长度运用到了lca 我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。 先把边按照权值排序，然...stl,tarjan,lca,dfs,倍增
[luoguP3258] [JLOI2014]松鼠的新家（lca + 树上差分）
传送门 需要把一条路径上除了终点外的所有数都 + 1， 比如，给路径 s t 上的权值 + 1，可以先求 x = lca(s，t) 类似数列上差分的思路，可以给 s 和 f[t] 的权值 + 1，给 ...lca,倍增,差分
[bzoj1787][Ahoi2008]Meet 紧急集合（lca）
传送门 可以看出，三个点两两之间的lca会有一对相同，而另一个lca就是聚集点。 然后搞搞就可以求出距离了。 ——代码 1 #include cstdio 2 #include cstring 3 #...lca,倍增
[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）
传送门 水题。 直接倍增求lca。 x到y的距离为dis[x] + dis[y] 2 * dis[lca(x, y)] ——代码 1 #include cstdio 2 #include cstrin...lca,倍增
NOIP2013D1T3货车运输（最大生成树+倍增lca）
传送门 这道题，先用kruskal求一遍图中的最大生成树。 然后，倍增求lca，求lca的同时求出边权的最小值。 #include cstring#include cstdio#include alg...最小生成树,lca,倍增
lca最近公共祖先（模板）
洛谷上的lca模板题—— 传送门 1.tarjan求lca 学了求lca的 tarjan算法（离线） ，在洛谷上做模板题，结果后三个点超时。 又把询问改成链式前向星，才ok。 这个 博客 ，tarja...模板,tarjan,倍增,lca,树链剖分
共1页/8条
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化