bzoj-1787-洛谷-4281（LCA板子题）
传送门（bzoj）传送门（洛谷）可以说这道也是一个板子题由于题中是三个人需经过的路径最短就会有一点点不太一样那么就两两求LCA这样之后就会出现两种状况一、所得到的三个LCA是相等的那毫无疑问真正的LCA的值就是这个值二、若不是第二种情况那必然会出现有且仅有一个LCA的值与令两个LCA的值不同第二种情...
2016vijos 6-1 松鼠聚会（LCA+卡空间)
求LCA，N=1e6，原空间限制8MB求LCA需要深度，需要跳跃一定距离的祖先，需要父节点把一个整数压成3个char，f[]存父节点g[],深度为奇数的点存往上跳576步能到的点，深度为偶数的点存深度如果深度为奇数的点要求它的深度，求他父节点的深度+1如果深度为偶数的点要求它往上跳576步的祖先，先...
BZOJ 4539: [Hnoi2016]树 [主席树 lca]
4539: [Hnoi2016]树题意：不想写。复制模板树的子树，查询两点间距离。终于有一道会做的题了......画一画发现可以把每次复制的子树看成一个大点来建一棵树，两点的lca一定在大点的lca里然后每个大点维护一坨信息：节点编号的区间范围，到根的距离，大点对应子树的根，大点是接在了模板树里哪个...
（RMQ版）LCA注意要点
inline int lca(int x,int y){ if(x>y) swap(x,y); return (h[rmq[log[y-x+]][x]]<h[rmq[log[y-x+]][y-near[y-x+]+]])? rmq[log[y-x+]][x]...
hdu2586（LCA最近公共祖先）
How far away ？Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3653 Accepted Submission(s): ...
HDU 5293 Tree chain problem 树形dp+dfs序+树状数组+LCA
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5293题意：给你一些链，每条链都有自己的价值，求不相交不重合的链能够组成的最大价值。题解：树形dp，对于每条链u，v，w，我们只在lca(u,v)的顶点上处理它让dp[i]表示以i为根的子树的最大值，su...
[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）
传送门水题。直接倍增求lca。x到y的距离为dis[x] + dis[y] - 2 * dis[lca(x, y)]——代码 #include <cstdio> #include <cstring> #include <iostream> #define MAXN...
BZOJ3881[Coci2015]Divljak——AC自动机+树状数组+LCA+dfs序+树链的并
题目描述Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。接下来会发生q个操作，操作有两种形式：“1 P”，Bob往自己的集合里添加了一个字符串P。“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的...
bzoj3631[JLOI2014 松鼠的新家 倍增lca+差分
裸的树上差分+倍增lca每次从起点到终点左闭右开，这就有一个小技巧，要找到右端点向左端点走的第一步，然后差分就好了#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>...
[BZOJ3631]:[JLOI2014]松鼠的新家（LCA+树上差分）
题目传送门题目描述松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后...
【BZOJ】1602: [Usaco2008 Oct]牧场行走（lca）
http://www.lydsy.com/JudgeOnline/problem.php?id=1602一开始以为直接暴力最短路，但是n<=1000, q<=1000可能会tle。显然我没有看到树的性质，树边只有n-1，且一个点一定能到达另一个点所以我们求出lca，然后记录从根到每个点的...
poj 3694 Network 边双连通+LCA
题目链接：http://poj.org/problem?id=3694题意：n个点，m条边，给你一个连通图，然后有Q次操作，每次加入一条边（A,B），加入边后，问当前还有多少桥，输出桥的个数。解题思路：先将原连通图边双连通缩点成一颗树，Q次操作过程中对树进行LCA操作。具体看代码：看网上也有不缩点的...
POJ 1470 Closest Common Ancestors （LCA，离线Tarjan算法）
Closest Common AncestorsTime Limit: 2000MS Memory Limit: 10000KTotal Submissions: 13372 Accepted: 4340DescriptionWrite a program that takes as input a...
HDU4409-LCA模拟
给一个家谱，回答给的操作结果。1）L 按照字典序排序儿子，输出整个家谱。2）b 求出所给name的所有兄弟。3）c 求出两个name的LCA读入数据时，我用一个curfather数组维护固定深度的爸爸，之后就可以方便的将所给的数据形式转换成邻接表建图，同时使用map存储name和id号。Tree结构...
HDU 5296 Annoying problem (LCA，变形)
题意：给一棵n个节点的树，再给q个操作，初始集合S为空，每个操作要在一个集合S中删除或增加某些点，输出每次操作后：要使得集合中任意两点互可达所耗最小需要多少权值。（记住只能利用原来给的树边。给的树边已经有向。10万个点，10万个操作）思路：只能用 O(nlogn)的复杂度。官方题解：重点也就是要找到...
ACM-ICPC 2018 徐州赛区网络预赛 J Maze Designer(最大生成树，倍增lca)
https://nanti.jisuanke.com/t/31462要求在一个矩形中任意选两个点都有唯一的通路，所以不会建多余的墙。要求满足上述情况下，建墙的费用最小。理解题意后容易想到首先假设全部墙都建起来，然后拆掉费用最大的边使图成为一棵树，就是求一颗最大生成树求出最大生成树后，求任意两点的距离...
UVA 11354 Bond（MST + LCA）
n<=50000, m<=100000的无向图，对于Q<=50000个询问，每次求q->p的瓶颈路。其实求瓶颈路数组maxcost[u][v]有用邻接矩阵prim的方法。但是对于这个题的n，邻接矩阵是存不下的。。。所以默默的抄了一遍大白书上的算法。。。先用kruskal求MS...
Tarjan应用:求割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)【转】【修改】
一、基本概念：1.割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。2.割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。3.点连通度：最小割点集合中的顶点数。4.割边(桥)：删掉它之后，图...
(转)Tarjan应用:求割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)
基本概念：1.割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。2.割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。3.点连通度：最小割点集合中的顶点数。4.割边(桥)：删掉它之后，图必然...
蓝皮书：异象石 【dfs序+lca】
题目详见蓝皮书【算法竞赛：进阶指南】。题目大意：就是给你一颗树，然后我们要在上面进行三种操作： 1.标记某个点 或者 2.撤销某个点的标记 以及 3.询问标记点在树上连通所需的最短总边权数据范围：点数以及操作数：1e5，边权：1e9（意思就是答案要 long long 存）。分析：这道题比...