2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest G Gangsters in Central City (LCA)

题意:

有一棵树,水源在根节点1,房子在叶子节点。有若干操作,操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水,可以通过切断边实现(如果某个叶子节点到根节点的路径上有一条边被切掉,那么就不能供水了。)对于每次操作后,问不给所有歹徒供水最少要切多少条边,并且问在切满足前面最小的情况下,最少使得多少个良民受影响。初始没有歹徒。

思路:

 

我们先考虑第一个问题。容易知道,假设与根相连的有k条边,那么最多只需要切k次,就切断了所有房子的水源。

也就是说,从最少切的次数角度的考虑,切与水源相连的边一定是最优的。

我们可以考虑把树根1去掉,这样得到k棵子树

然后可以预处理出,对于每个叶子节点,其非根的最远祖先是谁,也就是k棵子树的根节点都是谁。

那么对于每次出现歹徒,假设其非根的最远祖先是x,只需要切1-x这条边即可。

 

现在考虑第二个问题,在保证问题一最小的情况下,一个比较直观的想法是,我们尽量往低了切,也就是尽量往原理根的边上切,这样才能使收到影响的良民比较少。

容易想到,一个子树上该切的点是,所有被歹徒占领的坏点的LCA。这样可以使得受到影响的良民最少。

因为我们要得到受到影响的良民的数量,所以用siz[i]维护以i为根的子树的叶子数量,以及歹徒的数量。

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

因此这题就是写个LCA就可以了,切掉的坏点的dfs序可以用个set维护下。

 

 

 

 

hdu 3078 Network (LCA)

题目链接

题意:

一棵树,给出点权,问一条树链上第k大的点权,点权可以动态修改。

思路:

暴力即可orz(数据是真的水啊。

求路径上的点的时候需要用到LCA

 

 

codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)

题目链接

题意:

给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。

思路:

LCA还是一下就能想到的,rmq+dfs在线求。

然后我开始分情况讨论,讨论了一年也没讨论完,哭哭

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,然后分别求出K到a,b,c三点的路径长度,取最大值+1就是答案。

所以我的问题在于,没有试图往一般性的方向考虑,以为讨论一下就可以了…

这大概就是所谓的猜结论?

感性的理解的话,LCA越深,意味着另一个点到LCA的距离越远,也就是相交的路径越长

但是我的话,估计还是很难在短短不到一个小时内得出这样一般性的结论orz…

这大概就是数学方面的天赋差距把…T T

 

 

leetcode 235. Lowest Common Ancestor of a Binary Search Tree(求一个BST中某两个节点LCA)

题目链接

题意:求一个BST中某两个节点LCA….

思路:卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

两个节点的LCA的值一定在这两个节点之间。

可以根据这个条件做二分。。。

这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。

 

zoj 3195 Design the city (lca,dfs+rmq)

zoj 3195题目链接
题意:求树上三点的最短距离。。。
思路:两两求,和除以2.
因为忘记初始化p=0..WA了将近两个小时。。。?
妈的智障。

hdu 2874 Connections between cities (添加虚点,并查集+LCA(rmq+dfs))

hdu2874题目链接

题意:给一个森林,问两点的最短距离,或者输出两点不联通。

思路:最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

所谓虚点,就是之前假设某个不存在的点,有点类似做辅助线。

通过添加虚点,我们可以把这个森林转化成一棵树。

这样求两点的距离就可以转化成一棵树上的两点的距离。

用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。

不联通的话就是LCA 为0的情况(0是添加的虚点,作为新的树的根)

具体添加虚点的方法是:森林中每棵树的根连边到虚点上。权值大小随意,因为最后会抵消(?) 为了知道每棵树的根,需要用到并查集(其实根是随便定义的,但是森林中每棵树只能一个点和虚点相连不然就出现环了,所以需要用到并查集)

以及了解了(?)并查集的非递归的路径压缩写法。。。?

缺点是速度更慢,优点是不会爆栈。。。

还有需要学习一下按rank合并和按size合并的进阶并查集。。。?

以及:RE了好多次是因为。。。添加了虚点0,所以各种下标都应该是从0开始,初始化清空的时候忘了(从0开始)清vector…导致多组数据一直往edge[0]里面添加边。。。然后就炸了(手动微笑)

 

 

 

 

poj 1986 Distance Queries (lca,在线做法dfs+rmq)

题目链接
题意:求树上两点的最短距离?
思路: dis[i]表示点i到根节点的距离,那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)].
只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

 

 

poj 1470 Closest Common Ancestors (lca,rmq+dfs,读入技巧)

poj1470题目链接

题意:求两点的lca.
思路:dfs+rmq. 读入技巧。
读入比较坑爹。。。
学会了一种新的读入技巧。

scanf(“%2s”,st);

表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。

 

 

 

 

poj 1330 Nearest Common Ancestors (lca,用dfs+rmq在线求解)

poj1330题目链接

题意:给出一棵树,求两点的lca.
思路:将lca转化成rmq在线求解。

代码部分参考了:参考代码

感觉实现得很巧妙。。。
把树存成了有向图,dfs遇到的时候一定是第一次遇到,此时更新R.
然后第二次遇到某个点就是在回溯的时候了。

算法学习链接

hdu 2586 How far away ? (tarjan算法求LCA模板题)

题目链接
题意:一棵树,给出n-1个边权,然后q组查询,每组查询询问两个点之间的距离。
思路:

dfs跑出根到每个点的距离,设为dis[i]
那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];

其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥,其实也很直观。。不理解的话画个图就好。

所以终点就是求两个点的LCA.

据说有好多种做法。今天学习了大概是最简单的一种?
学习链接

 

我的理解:其实本质就是利用并查集。。在访问一个点的子树的时候,这个点其所有子树的祖先。。。由于祖先的节点比较小,所以merge的时候要f[大]=小…

要注意Tarjan 算法是离线算法。

哦对了。。这题要扩展语句才能过,不然会RE…