题目大意:给你一棵树,让你求结点 u 和 v 的最近公共祖先(即LCA)。
解题思路:这道题我学习了两种方法。一种是 tarjan 算法(dfs + 并查集) ,另一种是倍增法。tarjan算法是一种离线算法,较易理解,不再详述。着重谈一下在线算法 : 倍增法求LCA 。
tarjan 算法程序如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#define mem(a , b) memset(a , b , sizeof......
阅读全文