本文从WordPress迁移而来, 查看全部WordPress迁移文章
LCA模板题
题意:给一个无根树,有q个询问,每个询问两个点,问两点的距离。求出 lca = LCA(X,Y) , 然后dir[x] + dir[y] - 2 * dir[lca]
dir[u]表示点u到树根的距离
下面两份代码都可以通过HDU的C++和G++,都不存在爆栈问题,网上很多人说会爆栈,加了申请系统栈语句,其实不用,而且好想比赛中不允许使用的
Tarjan算法跑得更快些,C++ 15ms, G++ 50ms 左右, RMQ大概60ms
在线算法:LCA转化为RMQ
1 |
|
离线算法:Tarjan算法解决
1 |
|