最近公共祖先问题(LCA)1172. 祖孙询问 - AcWing题库
LCA模板题
#include<bits/stdc++.h> using namespace std; const int N = 40010, M = 2 * N; int n, m; int h[N], e[M], ne[M], idx; int depth[N], fa[N][16]; // depth存每个节点的深度,fa存倍增往前走2^i步到哪个点编号 int q[N]; // 数组模拟队列 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void bfs(int root) // 宽搜遍历图预处理fa数组,顺便预处理depth数组 { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[root] = 1; // 根节点深度为1,越界的话为0 int hh = 0, tt = 0; q[0] = root; while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q[++tt] = j; fa[j][0] = t; // j的父节点是t for (int k = 1; k <= 15; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1]; // 递推求fa数组 } } } } int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); // 保证a的深度大于b for (int k = 15; k >= 0; k--) if (depth[fa[a][k]] >= depth[b]) // a往上跳到和b同一个深度 a = fa[a][k]; if (a == b) return a; // 如果a和b是一个节点,直接返回即可 for (int k = 15; k >= 0; k--) if (fa[a][k] != fa[b][k]) // a和b同时往上跳,直到跳到公共祖先的子节点 { a = fa[a][k]; b = fa[b][k]; } return fa[a][0]; // 返回父节点即可 } int main(void) { cin >> n; int root; memset(h, -1, sizeof h); for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; if (b == -1) root = a; else add(a, b), add(b, a); } bfs(root); cin >> m; while (m--) { int a, b; cin >> a >> b; int p = lca(a, b); if (p == a) puts("1"); else if (p == b) puts("2"); else puts("0"); } return 0; }
1171. 距离 - AcWing题库
Tarjan离线算法求LCA,将所有询问读入后一次性输出
#include<bits/stdc++.h> using namespace std; const int N = 20010, M = N * 2; typedef pair<int, int> PII; int n, m; int h[N], e[M], w[M], ne[M], idx; int dist[N]; // 当前节点到根节点的距离 int p[N]; int res[N]; int st[N]; vector<PII> query[N]; // first存查询的另外一个点, second存查询编号 void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void dfs(int u, int fa) // 深搜预处理dist数组 { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dist[j] = dist[u] + w[i]; dfs(j, u); } } int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } void tarjan(int u) { st[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!st[j]) // 如果当前节点没有被遍历 { tarjan(j); p[j] = u; // 把当前点的祖宗节点更新为u } } for (auto item : query[u]) // 如果搜到叶子节点了,就开始更新答案 { int y = item.first, id = item.second; if (st[y] == 2) // { int anc = find(y); // 找到y的祖宗结点 res[id] = dist[u] + dist[y] - dist[anc] * 2; // 更新距离 } } st[u] = 2; // 把当前节点置为2,表示已经搜过 } int main(void) { cin >> n >> m; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; if (a != b) { query[a].push_back({b, i}); query[b].push_back({a, i}); } } for (int i = 1; i <= n; i++) p[i] = i; dfs(1, -1); // 任取一个根节点,然后把fa置为-1即可 tarjan(1); for (int i = 0; i < m; i++) cout << res[i] << endl; return 0; }
356. 次小生成树 - AcWing题库
利用LCA求次小生成树:
先建出最小生成树,然后枚举非树边,利用LCA求出非树边两端之间的最大边和次大边,最后返回的是和非树边的差值,最后求 m i n min min 即可
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010, M = 300010, INF = 0x3f3f3f3f; int n, m; struct Edge { int a, b, w; bool used; bool operator< (const Edge &t) const // 重载小于号排序 { return w < t.w; } }edge[M]; int p[N]; // 并查集数组 int h[N], e[M], w[M], ne[M], idx; // 邻接表 int depth[N], fa[N][17], d1[N][17], d2[N][17]; // d1最大边,d2次大边 int q[N]; // 队列 void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } LL kruskal() // 先求出最小生成树,并把树边标记上 { for (int i = 1; i <= n; i ++ ) p[i] = i; sort(edge, edge + m); LL res = 0; for (int i = 0; i < m; i ++ ) { int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w; if (a != b) { p[a] = b; res += w; edge[i].used = true; } } return res; } void build() // 把最小生成树建出来 { memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) if (edge[i].used) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; add(a, b, w), add(b, a, w); } } void bfs() // 宽搜预处理depth数组和fa数组 { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[1] = 1; // 0是哨兵,1是根节点 q[0] = 1; int hh = 0, tt = 0; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q[ ++ tt] = j; fa[j][0] = t; d1[j][0] = w[i], d2[j][0] = -INF; for (int k = 1; k <= 16; k ++ ) { int anc = fa[j][k - 1]; fa[j][k] = fa[anc][k - 1]; int dist[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]}; d1[j][k] = d2[j][k] = -INF; for (int u = 0; u < 4; u ++ ) { int d = dist[u]; if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d; else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d; } } } } } } int lca(int a, int b, int w) { static int dist[N * 2]; int cnt = 0; if (depth[a] < depth[b]) swap(a, b); for (int k = 16; k >= 0; k -- ) if (depth[fa[a][k]] >= depth[b]) { dist[cnt ++ ] = d1[a][k]; dist[cnt ++ ] = d2[a][k]; a = fa[a][k]; } if (a != b) { for (int k = 16; k >= 0; k -- ) if (fa[a][k] != fa[b][k]) { dist[cnt ++ ] = d1[a][k]; dist[cnt ++ ] = d2[a][k]; dist[cnt ++ ] = d1[b][k]; dist[cnt ++ ] = d2[b][k]; a = fa[a][k], b = fa[b][k]; } dist[cnt ++ ] = d1[a][0]; dist[cnt ++ ] = d1[b][0]; } int dist1 = -INF, dist2 = -INF; for (int i = 0; i < cnt; i ++ ) { int d = dist[i]; if (d > dist1) dist2 = dist1, dist1 = d; else if (d != dist1 && d > dist2) dist2 = d; } if (w > dist1) return w - dist1; if (w > dist2) return w - dist2; return INF; } int main() { cin >> n >> m; for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edge[i] = {a, b, c}; } LL sum = kruskal(); build(); bfs(); LL res = 1e18; for (int i = 0; i < m; i ++ ) if (!edge[i].used) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; res = min(res, sum + lca(a, b, w)); } cout << res << endl; return 0; }
352. 闇の連鎖 - AcWing题库
树上差分:
在一颗树上加边,必然会形成环,我们就对这条边两个端点求最近公共祖先,然后 d [ a ] + 1 , d [ b ] + 1 , d [ p ] − 2 d[a]+1, d[b]+1, d[p] - 2 d[a]+1,d[b]+1,d[p]−2 然后深搜求解即可
#include<bits/stdc++.h> using namespace std; const int N = 100010, M = 2 * N; int n, m; int h[N], e[M], ne[M], idx; int depth[N], fa[N][17]; int d[N]; int q[N]; int ans; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void bfs() // 预处理depth数组和fa数组 { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[1] = 1; int hh = 0, tt = 0; q[0] = 1; while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q[++tt] = j; fa[j][0] = t; for (int k = 1; k <= 16; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } int lca(int a, int b) // lca求最近公共祖先 { if (depth[a] < depth[b]) swap(a, b); for (int k = 16; k >= 0; k--) if (depth[fa[a][k]] >= depth[b]) a = fa[a][k]; if (a == b) return a; for (int k = 16; k >= 0; k--) if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } return fa[a][0]; } int dfs(int u, int fa) // 树上差分 { int res = d[u]; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j != fa) { int s = dfs(j, u); if (s == 0) ans += m; else if (s == 1) ans++; res += s; } } return res; } int main(void) { cin >> n >> m; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } bfs(); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; int p = lca(a, b); d[a]++, d[b]++, d[p] -= 2; } dfs(1, -1); cout << ans << endl ; return 0; }