思路
可以用倍增法去解决问题
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, root, parent[30][600005], dep[600005], head[1000005];
int log_v;
int cnt = 0;
struct e {
int to, next;
} edge[1000005];
int getint() {
char ch = '*';
while (!isdigit(ch = getchar()));
int num = ch - '0';
while (isdigit(ch = getchar()))num = num * 10 + ch - '0';
return num;
}
void add (int x, int y) {
cnt++;
edge[cnt].to = y;
edge[cnt].next = head[x];
head[x] = cnt;
}
void dfs(int node, int father, int d) {
parent[0][node] = father;
dep[node] = d;
for (int i = head[node]; i != -1; i = edge[i].next) {
if (edge[i].to != father) dfs(edge[i].to, node, d + 1);
}
}
void init() {
dfs(root, -1, 0);
for (int k = 0; k < log_v - 1; k++) {
for (int i = 1; i <= n; i++) {
if (parent[k][i] < 0) parent[k + 1][i] = -1;
else parent[k + 1][i] = parent[k][parent[k][i]];
}
}
}
int LCA(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
for (int i = 0; i < log_v; i++) {
if (((dep[y] - dep[x]) >> i) & 1) y = parent[i][y];
}
if (x == y) return x;
for (int i = log_v; i >= 0; i--) {
if (parent[i][x] != parent[i][y]) {
x = parent[i][x];
y = parent[i][y];
}
}
return parent[0][x];
}
int main() {
memset(head, -1, sizeof(head));
n = getint();
m = getint();
root = getint();
log_v = int(log10(n) / log10(2)) + 1;
for (int i = 1; i <= n - 1; i++) {
int x, y;
x = getint();
y = getint();
add(x, y);
add(y, x);
}
init();
for (int i = 1; i <= m; i++) {
int x, y;
x = getint();
y = getint();
printf("%d\n", LCA(x, y));
}
return 0;
}
标签:head,ch,parent,int,cnt,edge,luoguP3379,LCA,模板
From: https://www.cnblogs.com/mcr130102/p/18316355