Step1 Problem:
[原题] https://www.luogu.org/problem/P3379 给定一棵有根多叉树, 请求出指定两个点直接最近的公共祖先.
Step2 Ideas:
lca 模板题, 主要为了存模板. LCA(Least Common Ancestors), 即最近公共祖先, 是指在有根树中, 找出某两个结点 u 和 v 最近的公共祖先
Step3 Code: Tarjan, 离线算法, 时间复杂度 O(n + q)
- // luogu-judger-enable-o2
- #define _CRT_SECURE_NO_WARNINGS
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<bitset>
- #include<cassert>
- #include<cctype>
- #include<math.h>
- #include<cstdlib>
- #include<ctime>
- #include<deque>
- #include<iomanip>
- #include<list>
- #include<map>
- #include<queue>
- #include<set>
- #include<stack>
- #include<vector>
- #define lt k<<1
- #define rt k<<1|1
- #define lowbit(x) x&(-x)
- #define lson l,mid,lt
- #define rson mid+1,r,rt
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define iOS iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define mem(a, b) memset(a, b, sizeof(a))
- //#define int ll
- const double pi = acos(-1.0);
- const double eps = 1e-6;
- const double C = 0.57721566490153286060651209;
- const ll mod = 3e7;
- const int inf = 0x3f3f3f3f;
- const ll INF = 0x3f3f3f3f3f3f3f3f;
- const int maxn = 5e5+ 4000;
- struct node {
- int u, v, w, next;
- node () {}
- node(int u_, int v_, int w_, int next_) {
- u = u_;
- v = v_;
- w = w_;
- next = next_;
- }
- } edge[maxn <<1];
- struct nod {
- int u, v, id, next;
- nod() {}
- nod(int u_, int v_, int id_, int next_) {
- u = u_;
- v = v_;
- id = id_;
- next = next_;
- }
- }qu[maxn << 1];
- int n, m, ans;
- int head[maxn], head1[maxn];
- int cnt, cnt1;
- int res[maxn];
- int de[maxn], pre[maxn], fa[maxn];
- bool vis[maxn];
- void init() {
- cnt = cnt1 = 0;
- mem(vis, false);
- mem(de, 0);
- mem(head, -1);
- mem(head1, -1);
- mem(qu, 0);
- mem(edge, 0);
- for (int i = 1; i <= n; i++) fa[i] = i;
- }
- void add_edge(int u, int v, int w) {
- edge[cnt] = (node){ u, v, w, head[u] };
- head[u] = cnt++;
- }
- void add_qu(int u, int v, int id) {
- qu[cnt1] = (nod){ u, v, id, head1[u] };
- head1[u] = cnt1++;
- }
- int find_fa(int x) {
- if (x == fa[x]) return x;
- else return fa[x] = find_fa(fa[x]);
- }
- void Tarjan(int u) {
- vis[u] = true;
- for (int i = head[u]; ~i; i = edge[i].next) {
- int v = edge[i].v;
- if (!vis[v]) {
- Tarjan(v);
- int r1 = find_fa(u);
- int r2 = find_fa(v);
- if (r1 != r2) fa[r2] = r1;
- }
- }
- for (int i = head1[u]; ~i; i = qu[i].next) {
- int v = qu[i].v;
- if (vis[v]) res[qu[i].id] = find_fa(v);
- }
- }
- int main() {
- // freopen("testdata.in", "r", stdin);
- int s;
- cin>> n>> m>> s;
- init();
- for (int i = 1; i <n; i++) {
- int u, v;
- cin>> u>> v;
- add_edge(u, v, 1);
- add_edge(v, u, 1);
- }
- for (int i = 1; i <= m; i++) {
- int a, b;
- cin>> a>> b;
- add_qu(a, b, i);
- add_qu(b, a, i);
- }
- Tarjan(s);
- for (int i = 1; i <= m; i++) cout <<res[i] << endl;
- return 0;
- }
Step4 Code2: 倍增法求 lca, 在线算法, 时间复杂度 O(n logn)
- #define _CRT_SECURE_NO_WARNINGS
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<bitset>
- #include<cassert>
- #include<cctype>
- #include<math.h>
- #include<cstdlib>
- #include<ctime>
- #include<deque>
- #include<iomanip>
- #include<list>
- #include<map>
- #include<queue>
- #include<set>
- #include<stack>
- #include<vector>
- #define lt k<<1
- #define rt k<<1|1
- #define lowbit(x) x&(-x)
- #define lson l,mid,lt
- #define rson mid+1,r,rt
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define iOS iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define mem(a, b) memset(a, b, sizeof(a))
- //#define int ll
- const double pi = acos(-1.0);
- const double eps = 1e-6;
- const double C = 0.57721566490153286060651209;
- const ll mod = 3e7;
- const int inf = 0x3f3f3f3f;
- const ll INF = 0x3f3f3f3f3f3f3f3f;
- const int maxn = 5e5+ 4000;
- int lg[maxn], dep[maxn], fa[maxn][20], head[maxn];
- int cnt;
- int n, m, s;
- struct node {
- int v, next;
- } edge[maxn <<1];
- void add_edge(int u, int v) {
- edge[cnt].v = v;
- edge[cnt].next = head[u];
- head[u] = cnt++;
- }
- void init() {
- cnt = 0;
- for (int i = 1; i <= n; i++) {
- head[i] = -1;
- dep[i] = -1;
- lg[i] = lg[i - 1] + (1 << (lg[i - 1]) == i);
- }
- mem(fa, 0);
- }
- void dfs(int u, int fath) {
- dep[u] = dep[fath] + 1;
- fa[u][0] = fath;
- for (int i = 1; (1 << i) <= dep[u]; i++) {
- fa[u][i] = fa[fa[u][i - 1]][i - 1];
- }
- for (int i = head[u]; ~i; i = edge[i].next) {
- if (edge[i].v != fath) dfs(edge[i].v, u);
- }
- }
- int lca(int u, int v) {
- if (dep[u] < dep[v]) swap(u, v);
- while (dep[u]> dep[v]) u = fa[u][lg[dep[u] - dep[v]] - 1];
- if (u == v) return u;
- for (int i = lg[dep[u]] - 1; i>= 0; i--) {
- if (fa[u][i] != fa[v][i]) {
- u = fa[u][i];
- v = fa[v][i];
- }
- }
- return fa[u][0];
- }
- int main() {
- scanf("%d%d%d", &n, &m, &s);
- init();
- for (int i = 1; i <n; i++) {
- int u, v;
- cin>> u>> v;
- add_edge(u, v);
- add_edge(v, u);
- }
- dfs(s, 0);
- for (int i = 1; i <= m; i++) {
- int u, v;
- scanf("%d%d", &u, &v);
- printf("%d\n", lca(u, v));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3158914.html