LCA（Lowest Common Ancesor)
链式前向星模板
1 #include<iostream>
2 #include<cstring>
3 #include<cmath>
4 #define mem(a,x) memset(a,x,sizeof(a))
5 using namespace std;
6 const int N = 1e4 + 5;
7 int fa[N][15];
8 int head[N];
9 int vis[N];
10 int cur;
11 int depth[N];
12 bool Du[N];
13 int ans[N];
14 int n;
15 struct Edge {
16 int to;
17 int nex;
18 }edge[N];
19 void AddEdge(int u, int v) {
20 edge[cur].to = v;
21 edge[cur].nex = head[u];
22 head[u] = cur++;
23 }
24 void init() {
25 mem(head, -1);
26 mem(fa, 0);
27 mem(Du, 0);
28 mem(depth, 0);
29 cur = 0;
30 }
31 void dfs(int v, int p, int d) {
32 fa[v][0] = p;
33 depth[v] = d;
34 for (int i = head[v]; i != -1; i = edge[i].nex) {
35 dfs(edge[i].to, v, d + 1);
36 }
37 }
38 int LCA(int s, int t) {
39 if (depth[s] < depth[t])
40 swap(s, t);
41 int temp = depth[s] - depth[t];
42 for (int i = 0; (1 << i) <= temp; i++)
43 {
44 if ((1<<i)&temp)
45 s = fa[s][i];
46 }
47 if (s == t)return s;
48 for (int i = (int)log2(n*1.0); i >= 0; i--) {
49 if (fa[s][i] != fa[t][i]) {
50 s = fa[s][i];
51 t = fa[t][i];
52 }
53 }
54 return fa[s][0];
55 }
56 int main()
57 {
58 int T, s, t, root;
59 cin >> T;
60 while (T--)
61 {
62 init();
63 cin >> n;
64 for (int i = 0; i < n - 1; i++) {
65 cin >> s >> t;
66 AddEdge(s, t);
67 Du[t] = 1;
68 }
69 for (int i = 1; i <= n; i++){
70 if (Du[i] == 0){
71 root = i;
72 break;
73 }
74 }
75 dfs(root, -1, 0);
76 for (int j = 0; (1 << (j + 1)) < n; j++) {
77 for (int i = 1; i <= n; i++) {
78 if (fa[i][j] < 0)
79 fa[i][j + 1] = -1;
80 else fa[i][j + 1] = fa[fa[i][j]][j];
81 }
82 }
83 cin >> s >> t;
84 cout << LCA(s, t) << endl;
85 }
86 }
连接表模板
1 /* 2 邻接表存较慢 3 考虑链式前向星*/ 4 #include<iostream> 5 #include<cstring> 6 #include<cmath> 7 #include<vector> 8 #define mem(a,x) memset(a,x,sizeof(a)) 9 using namespace std; 10 const int N = 1e4 + 5; 11 int father[N][15]; 12 int depth[N]; 13 int Du[N]; 14 int max_log; 15 struct Node{ 16 vector<int>G; 17 }; 18 Node tree[N]; 19 void dfs(int v, int p, int d) { 20 father[v][0] = p; 21 depth[v] = d; 22 for (int i = 0; i < tree[v].G.size(); i++) { 23 if (tree[v].G[i] != p)dfs(tree[v].G[i], v, d + 1); 24 } 25 } 26 void init() { 27 memset(Du, 0, sizeof(Du)); 28 //for (int i = 0; i < 15; i++)G[i].clear(); 29 memset(tree, 0, sizeof(tree)); 30 memset(depth, 0, sizeof(depth)); 31 memset(father, 0, sizeof(father)); 32 } 33 int LCA(int u, int v) { 34 if (depth[u]>depth[v])swap(u, v); 35 int temp = depth[v] - depth[u]; 36 for (int i = 0; (1 << i) <= temp; i++) { 37 if ((1 << i)&temp) {//如果temp是1011,1分别左移1,2,3,4位，与temp&，如果当前temp在i为1，说明可以提高i位 38 v= father[v][i];//depth[v]大，先将v提高与u水平 39 } 40 } 41 if (u == v)return u; 42 for (int i = max_log; i >= 0; i--) { 43 if (father[u][i] != father[v][i]) { 44 u = father[u][i]; 45 v = father[v][i]; 46 } 47 } 48 return father[u][0]; 49 } 50 int main() { 51 int T, s, t, root; 52 cin >> T; 53 while (T--) 54 { 55 56 int n; 57 cin >> n; 58 init(); 59 max_log = int(log2(1.0*n)); 60 for (int i = 0; i < n - 1; i++) { 61 cin >> s >> t; 62 tree[s].G.push_back(t); 63 Du[t] = 1; 64 } 65 for (int i = 1; i <= n; i++) { 66 if (Du[i] == 0) { 67 root = i; 68 break; 69 } 70 } 71 dfs(root, -1, 0); 72 for (int j = 0; (1 << (j + 1)) < n; j++) { 73 for (int i = 1; i <= n; i++) { 74 if (father[i][j] < 0) 75 father[i][j + 1] = -1; 76 else father[i][j + 1] = father[father[i][j]][j]; 77 } 78 } 79 cin >> s >> t; 80 cout << LCA(s, t) << endl; 81 } 82 return 0; 83 }
树上距离 HDU-6115
1 #define _CRT_SECURE_NO_WARNINGS 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #define mem(a,x) memset(a,x,sizeof(a)) 8 const int INF = 0x3f3f3f3f; 9 using namespace std; 10 const int N = 100010; 11 int fa[N][25]; 12 int head[N]; 13 int cur; 14 int depth[N]; 15 int dis[N];//到根节点的距离 16 vector<int>vec[N]; 17 int n,m; 18 struct Edge { 19 int to; 20 int cost; 21 int nex; 22 }edge[2*N]; 23 //edge[i].to表示第i条边的终点,edge[i].nex表示与第i条边同起点的下一条边的存储位置,edge[i].cost为边权值. 24 //head[i]保存的是以i为起点的所有边中编号最大的那个, 而把这个当作顶点i的第一条起始边的位置 25 void AddEdge(int u, int v, int w) { 26 edge[cur].to = v; 27 edge[cur].cost = w; 28 edge[cur].nex = head[u]; 29 head[u] = cur++; 30 } 31 void init() { 32 mem(head, -1); 33 mem(fa, 0); 34 mem(depth, 0); 35 mem(dis, 0); 36 cur = 0; 37 } 38 void dfs(int v, int p, int d,int cost) { 39 fa[v][0] = p; 40 depth[v] = d; 41 dis[v] = cost; 42 for (int i = head[v]; i != -1; i = edge[i].nex) { 43 if(!depth[edge[i].to])//无向图 44 dfs(edge[i].to, v, d + 1,dis[v]+edge[i].cost); 45 } 46 } 47 /* 48 void dfs(int v, int f, int cost) 49 { 50 dis[v] = cost; 51 for (int i = head[v]; i != -1; i = edge[i].nex) 52 { 53 int u = edge[i].to; 54 if (u == f) continue; 55 if (!depth[u]) 56 depth[u] = depth[v] + 1, fa[u][0] = v, dfs(u, v, dis[v] + edge[i].cost); 57 } 58 } 59 */ 60 int LCA(int s, int t) { 61 if (depth[s] < depth[t]) 62 swap(s, t); 63 int temp = depth[s] - depth[t]; 64 for (int i = 0; (1 << i) <= temp; i++) 65 { 66 if ((1 << i)&temp) 67 s = fa[s][i]; 68 } 69 if (s == t)return s; 70 for (int i = (int)log2(n*1.0); i >= 0; i--) { 71 if (fa[s][i] != fa[t][i]) { 72 s = fa[s][i]; 73 t = fa[t][i]; 74 } 75 } 76 return fa[s][0]; 77 } 78 int main() 79 { 80 int T, s, t,w, root; 81 scanf("%d", &T); 82 while (T--) 83 { 84 init(); 85 scanf("%d%d", &n, &m); 86 for (int i = 0; i < n - 1; i++) { 87 scanf("%d%d%d", &s, &t, &w); 88 AddEdge(s, t,w); 89 AddEdge(t, s, w); 90 //Du[t] = 1; 91 } 92 //找到根节点 93 94 for (int i = 1; i <= m; i++) 95 { 96 int num, v; 97 scanf("%d", &num); 98 for (int j = 1; j <= num; j++) 99 { 100 scanf("%d", &v); 101 vec[i].push_back(v); 102 } 103 } 104 //选择1为根 105 dfs(1, -1,0,0); 106 for (int j = 0; (1 << (j + 1)) < n; j++) { 107 for (int i = 1; i <= n; i++) { 108 if (fa[i][j] < 0) 109 fa[i][j + 1] = -1; 110 else fa[i][j + 1] = fa[fa[i][j]][j]; 111 } 112 } 113 int q; 114 scanf("%d",&q); 115 for (int i = 1; i <= q; i++) 116 { 117 int v, u, ans = INF; 118 scanf("%d%d", &v, &u); 119 for (int j = 0; j < vec[v].size(); j++) 120 for (int k = 0; k < vec[u].size(); k++) 121 ans = min(ans, dis[vec[v][j]] + dis[vec[u][k]] - dis[LCA(vec[v][j], vec[u][k])] * 2); 122 printf("%d ", ans); 123 } 124 for (int i = 1; i <= m; i++) vec[i].clear(); 125 } 126 return 0; 127 }