hdu 2586 How far away ? ( 离线 LCA ， tarjan )
How far away ？Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10312 Accepted Submission(s):...
hdu 2586 How far away? （LCA模板）
题意：N个点，形成一棵树，边有长度。M个询问，每个询问(a,b)，询问a和b的距离思路：模板题，看代码。DFS预处理算出每个结点离根结点的距离。注意：qhead[maxn]，而不是qhead[maxm]。输出用%I64d，不要用%lld。C++ RE后 尝试用 G++交。代码：struct node...
POJ 1330 Nearest Common Ancestors(Tarjan离线LCA)
DescriptionA rooted tree is a well-known data structure in computer science and engineering. An example is shown below: In the figure, each node is l...
HDU 4409 Family Name List --乱搞、LCA
题意： 给出一些名字，名字间有父子关系，有三种操作：1.按祖先到后代，兄弟间按字典序由小到大排序，然后输出2.求某个节点的兄弟节点有多少个，包括自己（注意，根节点的兄弟节点是1）3.求节点a和b的公共祖先 （注意：如果公共祖先是a或b，必须要输出其父亲，与传统的LCA可以是自己不同）解法： 先把整棵...
Count on a tree SPOJ - COT （主席树，LCA）
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.We will ask you to perform the following o...
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)的复杂度。官方题解：重点也就是要找到...