LCA (最近公共祖先) Tarjan 倍增
LCA Tarjan：
实现原理
理解：离线算法，建好树后再查询，一次DFS 吧所有查询解决完。
时间复杂度：O(n+q)；
n个点 q次询问
补一下：链式向前星，并查集 ，Tarjan代码
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 5e5+ 10;
int fa[MAXN], head[MAXN], head_ask[MAXN], cnt, cnt_ask, ans[MAXN];
bool vis[MAXN];
int n, m, s;
struct Edge{
int to, dis, next;
int num;
}edge[MAXN << 1], ask[MAXN <> n >> m >> s;
int x, y;
init();
for(int i = 1; i > x >> y;
add_edge(x, y, 0);
add_edge(y, x, 0);
}
for(int i = 1; i > x >> y;
add_ask(x, y, i);
add_ask(y, x, i);
}
Tarjan(s);
for(int i = 1; i <= m; ++i) {
cout << ans[i] << endl;
}
}
练习题：
洛谷 P3379
LCA 倍增：
倍增原理
理解：
1) 在线算法
2）暴力的优化，不是一步一步向上找节点，每次走
步
模板待补
Harington
原创文章 207获赞 174访问量 7万+
关注
私信
展开阅读全文
作者：Harington
