dfs倍增写法
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 4e4 + 10, inf = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
std::vector<int> adj[N];
vector<int> dep(N, inf);
vector fa(N, vector<int>(16));
auto dfs = [&](auto self, int x, int father) -> void {
dep[x] = dep[father] + 1;
fa[x][0] = father;
for (int i = 1; i <= 15; i ++ ) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (int y : adj[x]) {
if (y != father) {
self(self, y, x);
}
}
};
auto lca = [&](int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
for (int k = 15; k >= 0; k -- ) {
if (dep[fa[u][k]] >= dep[v]) {
u = fa[u][k];
}
}
if (u == v) {
return u;
}
for (int k = 15; k >= 0; k -- ) {
if (fa[u][k] != fa[v][k]) {
u = fa[u][k];
v = fa[v][k];
}
}
return fa[u][0];
};
int root;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
if (v == -1) {
root = u;
} else {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
dfs(dfs, root, 0);
int m;
cin >> m;
while (m -- ) {
int u, v;
cin >> u >> v;
int p = lca(u, v);
if (p == u) {
cout << "1\n";
} else if (p == v) {
cout << "2\n";
} else {
cout << "0\n";
}
}
return 0;
}
bfs倍增写法
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 4e4 + 10, inf = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int root;
std::vector<int> adj[N];
for (int i = 0; i < n; i ++ ) {
int u, v;
cin >> u >> v;
if (v == -1) {
root = u;
} else {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
vector<int> dep(N, inf);
vector fa(N, vector<int>(16));
auto bfs = [&](int root) {
queue<int> q;
q.push(root);
dep[0] = 0;
dep[root] = 1;
while (q.size()) {
auto u = q.front();
q.pop();
for (auto v : adj[u]) {
if (dep[v] > dep[u] + 1) {
dep[v] = dep[u] + 1;
q.push(v);
fa[v][0] = u;
for (int k = 1; k <= 15; k ++ ) {
fa[v][k] = fa[fa[v][k - 1]][k - 1];
}
}
}
}
};
bfs(root);
auto lca = [&](int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
for (int k = 15; k >= 0; k -- ) {
if (dep[fa[u][k]] >= dep[v]) {
u = fa[u][k];
}
}
if (u == v) {
return u;
}
for (int k = 15; k >= 0; k -- ) {
if (fa[u][k] != fa[v][k]) {
u = fa[u][k];
v = fa[v][k];
}
}
return fa[u][0];
};
int m;
cin >> m;
while (m -- ) {
int u, v;
cin >> u >> v;
int p = lca(u, v);
if (p == u) {
cout << "1\n";
} else if (p == v) {
cout << "2\n";
} else {
cout << "0\n";
}
}
return 0;
}
tarjan算法
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 4e4 + 10;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> g[N];
vector<pair<int, int>> query[N];
vector<int> f(N), ans(n + 1);
bitset<N> vis;
iota(f.begin(), f.end(), 0);
auto find = [&](int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
};
auto tarjan = [&](auto self, int u) -> void {
vis[u] = true;
for (auto v : g[u]) {
if (!vis[v]) {
self(self, v);
f[v] = u;
}
}
for (auto q : query[u]) {
int v = q.first, i = q.second;
if (vis[v]) {
ans[i] = find(v);
}
}
};
int root;
for (int i = 1; i <= n; i ++ ) {
int u, v;
cin >> u >> v;
if (v == -1) {
root = u;
} else {
g[u].push_back(v);
g[v].push_back(u);
}
}
int m;
cin >> m;
pair<int, int> req[N];
for (int i = 1; i <= m; i ++ ) {
int a, b;
cin >> a >> b;
query[a].push_back({b, i});
query[b].push_back({a, i});
req[i] = {a, b};
}
tarjan(tarjan, root);
for (int i = 1; i <= m; i ++ ) {
if (ans[i] == req[i].first) {
cout << "1\n";
} else if (ans[i] == req[i].second) {
cout << "2\n";
} else {
cout << "0\n";
}
}
return 0;
}
树链剖分
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 4e4 + 10;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> siz(N), top(N), dep(N), parent(N);
vector<std::vector<int>> adj;
adj.assign(N, {});
auto addEdge = [&](int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
};
auto dfs1 = [&](auto self, int u) -> void {
if (parent[u] != -1) {
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
}
siz[u] = 1;
for (auto &v : adj[u]) {
parent[v] = u;
dep[v] = dep[u] + 1;
self(self, v);
siz[u] += siz[v];
if (siz[v] > siz[adj[u][0]]) {
std::swap(v, adj[u][0]);
}
}
};
auto dfs2 = [&](auto self, int u) -> void {
for (auto v : adj[u]) {
top[v] = v == adj[u][0] ? top[u] : v;
self(self, v);
}
};
auto lca = [&](int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
};
int root;
for (int i = 1; i <= n; i ++ ) {
int u, v;
cin >> u >> v;
if (v == -1) {
root = u;
} else {
addEdge(u, v);
}
}
top[root] = root;
dep[root] = 0;
parent[root] = -1;
dfs1(dfs1, root);
dfs2(dfs2, root);
int m;
cin >> m;
while (m--) {
int x, y;
cin >> x >> y;
int l = lca(x, y);
if (l == x) {
cout << "1\n";
} else if (l == y) {
cout << "2\n";
} else {
cout << "0\n";
}
}
return 0;
}