POJ 1470 Closest Common Ancestors tarjan LCA

题目没写多case,然而却是多case题,坑死了…

POJ 1330 Nearest Common Ancestors 倍增LCA

POJ 1330 Nearest Common Ancestors ST表LCA

hdu 6393Traffic Network in Numazu 基环外向树 LCA 树

题意就是,给你一个基环外向树,然后问任意两点间最短路,有修改边权,nlogn做法。

然后就在环上随便删一个遍,然后我们lca求最短路,再看经过删掉的边的距离,取个min就好了。这题数据很有趣,最后一条边一定在环上,可以少写一个dfs……

然后怎么修改边权,线段树按照dfs序维护一[……]

Read more

bzoj 3732: Network 倍增lca kruscal

倍增lca里面注意返回值前上爬的最后一步,不要忘了。还有不要把数组名写混了。

在最小生成树上跑倍增lca即可。

bzoj 2815: [ZJOI2012]灾难 lca

挺神的一道题。

我们考虑存在一种灭绝树。一种生物的灭绝会导致其子树灭绝。这样我们就可以解出题目所需答案。我们考虑如何构建这棵树。我们考虑如果一个生物吃a1,a2……an这些食物,那么显然在灭绝树上这些a的lca灭绝会导致这个生物灭绝。否则必然还有可行的食物链。那我们就可以把这个生物挂在lca下[……]

Read more

bzoj 1787: [Ahoi2008]Meet 紧急集合 倍增lca

大概猜一猜,证一证,发现两两得出3个lca,然后我们发现有两个是相同的,另外一个就是集合点。然后吧两两lca求和然后/2就是总共的路径长度。

bzoj 3631: [JLOI2014]松鼠的新家 tarjanlca 树状差分

我们用tarjan 求出所有的lca,然后我们只要用树状差分区间修改一下就行,最后线性求出每个点的值。开始我默认a1 = 1,然后就gg。

差分为当前节点的值减去所有孩子节点的差分值。然后我们最后只要根据bfs倒叙推一下就好啦。

Read more