首页 > 代码库 > [算法整理]树上求LCA算法合集
[算法整理]树上求LCA算法合集
1#树上倍增
以前写的博客:http://www.cnblogs.com/yyf0309/p/5972701.html
预处理时间复杂度O(nlog2n)，查询O(log2n),也不算难写。
2#st表(RMQ)
首先对一棵树进行dfs,得到欧拉序列，记录下每个节点的第一次出现位置。
（先序遍历这棵树，访问到的节点(无论是从深的一层返回还是父节点访问)就加入到序列中，序列长度为2 * n - 1）
根据欧拉序列神奇的特性，两个点第一次出现的位置之间，深度最小的一个点，是这两个点LCA（反正我是不会证明）。于是可以干什么呢？就建st表就行了。
预处理时间复杂度O(2nlog2(2n) + n)，查询时间复杂度O(log2n)。
codevs 商务旅行:
1 /** 2 * codevs 3 * Problem#1036 4 * Accepted 5 * Time:52ms 6 * Memory:2736k 7 */ 8 #include<iostream> 9 #include<sstream> 10 #include<cstdio> 11 #include<cmath> 12 #include<cstdlib> 13 #include<cstring> 14 #include<cctype> 15 #include<queue> 16 #include<set> 17 #include<map> 18 #include<stack> 19 #include<vector> 20 #include<algorithm> 21 #ifndef WIN32 22 #define AUTO "%I64d" 23 #else 24 #define AUTO "%lld" 25 #endif 26 using namespace std; 27 typedef bool boolean; 28 #define smin(a, b) (a) = min((a), (b)) 29 #define smax(a, b) (a) = max((a), (b)) 30 template<typename T> 31 inline void readInteger(T& u){ 32 char x; 33 int aFlag = 1; 34 while(!isdigit((x = getchar())) && x != ‘-‘); 35 if(x == ‘-‘){ 36 aFlag = -1; 37 x = getchar(); 38 } 39 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 40 ungetc(x, stdin); 41 u *= aFlag; 42 } 43 44 template<typename T>class Matrix{ 45 public: 46 T *p; 47 int lines; 48 int rows; 49 Matrix():p(NULL){ } 50 Matrix(int rows, int lines):lines(lines), rows(rows){ 51 p = new T[(lines * rows)]; 52 } 53 T* operator [](int pos){ 54 return (p + pos * lines); 55 } 56 }; 57 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) 58 59 ///map template starts 60 typedef class Edge{ 61 public: 62 int end; 63 int next; 64 Edge(const int end = 0, const int next = 0):end(end), next(next){} 65 }Edge; 66 typedef class MapManager{ 67 public: 68 int ce; 69 int *h; 70 Edge *edge; 71 MapManager(){} 72 MapManager(int points, int limit):ce(0){ 73 h = new int[(const int)(points + 1)]; 74 edge = new Edge[(const int)(limit + 1)]; 75 memset(h, 0, sizeof(int) * (points + 1)); 76 } 77 inline void addEdge(int from, int end){ 78 edge[++ce] = Edge(end, h[from]); 79 h[from] = ce; 80 } 81 inline void addDoubleEdge(int from, int end){ 82 addEdge(from, end); 83 addEdge(end, from); 84 } 85 Edge& operator[] (int pos) { 86 return edge[pos]; 87 } 88 }MapManager; 89 #define m_begin(g, i) (g).h[(i)] 90 ///map template ends 91 92 int n, m; 93 int cnt = 0; 94 Matrix<int> st; 95 int* seq; 96 int *dep, *app; 97 MapManager g; 98 const int P = 15; 99 int *mlog2;100 101 inline void init() {102 readInteger(n);103 g = MapManager(n, 2 * n);104 seq = new int[(const int)(2 * n + 1)];105 dep = new int[(const int)(n + 1)];106 app = new int[(const int)(n + 1)];107 for(int i = 1, a, b; i < n; i++){108 readInteger(a);109 readInteger(b);110 g.addDoubleEdge(a, b);111 }112 dep[0] = 0;113 }114 115 void dfs(int node, int f) {116 seq[++cnt] = node;117 dep[node] = dep[f] + 1;118 app[node] = cnt;119 for(int i = m_begin(g, node); i != 0; i = g[i].next) {120 int& e = g[i].end;121 if(e == f) continue;122 dfs(e, node);123 seq[++cnt] = node;124 }125 }126 127 inline void init_log() {128 mlog2 = new int[(const int)(2 * n + 1)];129 mlog2[1] = 0;130 for(int i = 2; i <= 2 * n; i++)131 mlog2[i] = mlog2[i / 2] + 1; 132 }133 134 inline void init_st() {135 init_log();136 st = Matrix<int>(cnt, mlog2[cnt] + 1);137 for(int i = 1; i <= cnt; i++)138 st[i][0] = seq[i];//,cout << i << " " << 0 << ":" << st[i][0] << endl;139 for(int j = 1; j <= P; j++)140 for(int i = 1; i + (1 << j) - 1 <= cnt; i++)141 st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) ? (st[i][j - 1]) : (st[i + (1 << (j - 1))][j - 1]);142 // cout << i << " " << j << ":" << st[i][j] << endl;143 }144 145 inline int lca(int a, int b) {146 if(app[a] > app[b]) swap(a, b);147 int pos = mlog2[app[b] - app[a] + 1];148 int u = st[app[a]][pos];149 int v = st[app[b] - (1 << pos) + 1][pos];150 return (dep[u] > dep[v]) ? (v) : (u);151 }152 153 int last;154 int dist;155 inline void solve() {156 readInteger(m);157 readInteger(last);158 for(int i = 1, a; i < m; i++){159 readInteger(a);160 int l = lca(a, last);161 dist += dep[a] + dep[last] - 2 * dep[l];162 last = a;163 }164 printf("%d", dist);165 }166 167 int main() {168 init();169 dfs(1, 0);170 init_st();171 solve();172 return 0;173 }
3#Tarjan算法（离线算法）
Tarjan需要一个并查集来辅助。
算法思路大概是这样:
init:初始化并查集，对查询建一个邻接链表，还是按照存边的方式，要双向的,再用一个数组记录第i个询问是否解决了。
1.访问子树
2.每次访问结束后将子树的并查集中的父节点指向当前节点。
3.子树都访问完了后，开始处理以该节点为起点的询问，如果终点已经被访问过了并且没有被解决，那么这个点和终点的LCA是终点在并查集中的父节点，然后再记录是否解决的那个数组中把对应位置设上true。
（画画图，试着举点反例(当然不存在)还是很容易理解的）
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifndef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class Edge { 38 public: 39 int end; 40 int next; 41 int w; 42 Edge(const int end = 0, const int next = 0, const int w = 0):end(end), next(next), w(w){ } 43 }Edge; 44 45 typedef class MapManager{ 46 public: 47 int ce; 48 Edge* edges; 49 int* h; 50 MapManager():ce(0), edges(NULL), h(NULL){ } 51 MapManager(int points, int limit):ce(0){ 52 edges = new Edge[(const int)(limit + 1)]; 53 h = new int[(const int)(points + 1)]; 54 memset(h, 0, sizeof(int) * (points + 1)); 55 } 56 inline void addEdge(int from, int end, int w){ 57 edges[++ce] = Edge(end, h[from], w); 58 h[from] = ce; 59 } 60 inline void addDoubleEdge(int from, int end, int w){ 61 addEdge(from, end, w); 62 addEdge(end, from, w); 63 } 64 Edge& operator [](int pos){ 65 return edges[pos]; 66 } 67 }MapManager; 68 #define m_begin(g, i) (g).h[(i)] 69 70 typedef class union_found{ 71 public: 72 int *f; 73 union_found():f(NULL) {} 74 union_found(int points) { 75 f = new int[(const int)(points + 1)]; 76 } 77 int find(int x) { 78 if(f[x] != x) return f[x] = find(f[x]); 79 return f[x]; 80 } 81 void unit(int fa, int so) { 82 int ffa = find(fa); 83 int fso = find(so); 84 f[fso] = ffa; 85 } 86 int& operator [](int pos){ 87 return f[pos]; 88 } 89 }union_found; 90 91 int n, m; 92 MapManager g; 93 MapManager q; 94 int *results; 95 boolean* enable; 96 int *querya, *queryb; 97 union_found uf; 98 boolean* visited; 99 int* dist;100 101 inline void init(){102 readInteger(n);103 g = MapManager(n, 2 * n);104 for(int i = 1, a, b, c; i < n; i++){105 readInteger(a);106 readInteger(b);107 readInteger(c);108 g.addDoubleEdge(a, b, c);109 }110 readInteger(m);111 q = MapManager(n, 2 * m);112 querya = new int[(const int)(m + 1)];113 queryb = new int[(const int)(m + 1)];114 results = new int[(const int)(m + 1)];115 enable = new boolean[(const int)(m + 1)];116 dist = new int[(const int)(n + 1)];117 uf = union_found(n);118 visited = new boolean[(const int)(n + 1)];119 memset(visited, false, sizeof(boolean) * (n + 1));120 memset(enable, true, sizeof(boolean) * (m + 1));121 for(int i = 1; i <= m; i++){122 readInteger(querya[i]);123 readInteger(queryb[i]);124 q.addDoubleEdge(querya[i], queryb[i], i);125 }126 dist[1] = 0;127 }128 129 void tarjan(int node, int f){130 uf[node] = node;131 visited[node] = true;132 for(int i = m_begin(g, node); i != 0; i = g[i].next){133 int& e = g[i].end;134 if(e == f) continue;135 dist[e] = dist[node] + g[i].w;136 tarjan(e, node);137 uf[e] = node;138 }139 for(int i = m_begin(q, node); i != 0; i = q[i].next) {140 int& e = q[i].end;141 if(visited[e] && enable[q[i].w]){142 int lca = uf.find(e);143 results[q[i].w] = lca;144 enable[q[i].w] = false;145 }146 }147 }148 149 inline void solve(){150 tarjan(1, 0);151 for(int i = 1; i <= m; i++){152 int dis = dist[querya[i]] + dist[queryb[i]] - 2 * dist[results[i]];153 printf("%d\n", dis);154 }155 }156 157 int main(){158 init();159 solve();160 return 0;161 }
[算法整理]树上求LCA算法合集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。