Recent public ancestors
topic:/?pid=2586
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
//
const int N = 50010;
int f[N][20], d[N], dist[N];
int e[2*N], ne[2*N], w[2*N], h[2*N], idx;
int n, m, t;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
std::queue<int> q;
void bfs() {
(1); // Add root node
d[1] = 1; // The level of the root node is 1
while (()) {
int x = ();
();
for (int i = h[x]; i != -1; i = ne[i]) {
int y = e[i];
if (d[y] != -1) continue; // y has been traversed and the depth has been assigned to it
d[y] = d[x] + 1; // The level of y is equal to the level of x plus one
dist[y] = dist[x] + w[i]; // The distance from y to the root node is the distance from x to the root node plus the size of the edge (x,y)
f[y][0] = x; // y moves upwards to 2 to reach x
for (int j = 1; j <= t; j ++) {
f[y][j] = f[f[y][j-1]][j-1]; // The point you reach when you walk y upwards 2^j step is: the point you reach when you walk y upwards 2^(j-1) step, and then upwards 2^(j-1) step
}
(y); // Join the queue
}
}
}
int lca(int x, int y) {
if (d[x] < d[y]) std::swap(x, y); // Make the level of x greater than the level of y
for (int i = t; i >= 0; i --) {
if (d[f[x][i]] >= d[y]) {
// The steps to the power of x are still greater than the depth of y, so you have to continue walking
x = f[x][i];
}
}
if (x == y) return y; // After the walk, x and y are equal, then y is the most recent public ancestor. Because y has a relatively large depth, y should be the ancestor
// Otherwise, the depths of these two points should be equal
for (int i = t; i >= 0; i --) {
// Move up at the same time
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0]; // In the end, the parent node of these two points is the nearest public ancestor
}
int main()
{
int T;
std::cin >> T;
while (T --) {
std::cin >> n >> m;
t = (int)(log(n) / log(2)) + 1;
// Clear
memset(h, -1, sizeof h);
memset(d, -1, sizeof d);
idx = 0;
// Read into a tree
for (int i = 1; i < n; i ++) {
int x, y, z;
std::cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
bfs(); // Preprocessing information
// answer the questions
for (int i = 1; i <= m; i ++) {
int x, y;
std::cin >> x >> y;
std::cout << dist[x] + dist[y] - 2 * dist[lca(x, y)] << "\n"; // The distance between two points is the sum of the distance between the two points and the root node minus 2 times the distance between the closest public ancestor and the root node
}
}
return 0;
}Several important points
1. t: The longest path from the leaf node to the root node (to the power of 2)
t = (int)(std::log(n) / std::log(2)) + 1;
2. f[i][j]: The point that can be reached by walking upward from point i to the power of 2^j, such as f[i][0] = father[i] (go upward from step 2^0 to reach the parent node)
When traversing the child node of the current node x and using y, the method of f[y][j] is as follows:
f[y][0] = x;
for (int j = 1; j <= t; j ++) {
f[y][j] = f[f[y][j-1]][j-1]; // The point you reach when you walk y upwards 2^j step is: the point you reach when you walk y upwards 2^(j-1) step, and then upwards 2^(j-1) step
}3. d[x]: The depth of point x, its parent node is represented by px
Initialize the d array to -1 to determine whether the current point has been traversed. If the current point is not traversed, then d[x] = d[px] + 1;
4. dist[x]: The distance from point x to the root node, its parent node is represented by px, and the weight of edge (px, x) is represented by w[i]
Initialize the d array to 0. If the current point has not been traversed, then dist[x] = dist[px] + w[i];
5. Find the nearest common ancestor of x and y:
If the depth of x is less than the depth of y, exchange x and y, and unified as the depth of x is greater than or equal to the depth of y
for (int i = t; i >= 0; i --) {
if (d[f[x][i]] >= d[y]) {
// The steps to the power of x are still greater than the depth of y, so you have to continue walking
x = f[x][i];
}
}After executing the above code, the depth of x and y may be the same, or x is equal to y (y is the ancestor of x)
-------1) If x and y are equal, then return y directly, and y is the most recent public ancestor
-------2) Otherwise, the depth of x and y is the same, and go up together
for (int i = t; i >= 0; i --) {
// Move up at the same time
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}After this end, they should meet the upward 2^i power steps and they are equal.
The last parent node of x is f[x][0], which is the answer