LCA

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 }

View Code

连接表模板

 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 }

View Code

树上距离 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\n", ans);
123         }
124         for (int i = 1; i <= m; i++) vec[i].clear();
125     }
126     return 0;
127 }