题意:现实给你一棵树然后给你树上的n-1条边,接着给你一对顶点,然后让你求这对顶点的LCA。
思路:由于刚刚学习LCA所以找了这一道最最水的LCA题目来做发现用复杂度较高的算法也能过,就是先遍历求出每个结点的父亲和深度,然后再将深度深的向上走,一直走到两个结点在同一高度上。再两个节点一起往上走,直到走到一个节点那么这个节点即为那两个节点的LCA。
代码如下:
1 //LCA 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cstring> 7 #include <algorithm> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #define MP(a, b) make_pair(a, b) 14 #define PB(a) push_back(a) 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef pair<int ,int> pii; 20 typedef pair<unsigned int, unsigned int> puu; 21 typedef pair<int ,double> pid; 22 typedef pair<ll, int> pli; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int LEN = 100000+10; 27 vector<int> Map[LEN]; 28 int root, ind[LEN], depth[LEN], parent[LEN]; 29 30 void dfs(int v, int p, int d){ 31 parent[v] = p; 32 depth[v] = d; 33 for(int i=0; i<Map[v].size(); i++){ 34 if(Map[v][i] != p)dfs(Map[v][i], v, d+1); 35 } 36 } 37 38 void init() {dfs(root, -1, 0);} 39 40 int lca(int u, int v){ 41 while(depth[u] > depth[v]) u = parent[u]; 42 while(depth[v] > depth[u]) v = parent[v]; 43 while(u!=v){ 44 u = parent[u]; 45 v = parent[v]; 46 } 47 return u; 48 } 49 50 int main() 51 { 52 // freopen("in.txt", "r", stdin); 53 54 int n, a, b, T; 55 scanf("%d", &T); 56 while(T--){ 57 for(int i=0; i<LEN; i++)Map[i].clear(); 58 memset(ind, 0, sizeof ind); 59 scanf("%d", &n); 60 for(int i=0; i<n-1; i++){ 61 scanf("%d%d", &a, &b); 62 Map[a].PB(b); 63 Map[b].PB(a); 64 ind[b]++; 65 } 66 for(int i=1; i<=n; i++) 67 if(ind[i]==0) {root = i;break;} 68 init(); 69 scanf("%d%d", &a, &b); 70 int ans = lca(a, b); 71 printf("%d\n", ans); 72 } 73 return 0; 74 }