Recent public ancestor (LCA) online practices

The ancestors

In a rooted tree , The points passed by are called ancestors , For general painting, we also make a point itself an ancestor , In this way, each point will have many ancestors , The recent common ancestor is , Give us two points , The nearest common ancestor to them is the nearest common ancestor , Pictured

If two points overlap , The recent public ancestor is itself

How to find

Upward marking method （ Not commonly used ）

Start at a point , To the root node , In the process of traversal , Mark all the dots he passed , Then do the same from another point , When we first came to the marked point, it was the nearest common ancestor , This time complexity is O(n) Of

Multiply

First, preprocess each point to go up $2^k$ Who is Bu's father .
fa[i][j] From i Start , Go up $2^j$ All nodes that can be reached by step , 0 <= j <= logn( With 2 Bottom )

Preprocess in a recursive way

Pictured , That is to say, from i This point starts , Go up $2^j$ Step , Point after , Next, there are two situations , The first is j=0, The answer is i Parent node , When j>0 When , It's divided into two steps , First jump to $2^{j-1}$, Then jump back from this point $2^{j-1}$ Step , Just like the picture

depth[] Expressing depth , The specified root node depth is 1, Then the depth of the sub node of the root node is 2, The sub node depth is 3, And so on , Is the distance to the root node +1

Both arrays can be used dfs perhaps bfs Come and ask for

distance

seek xy The common ancestor of these two points , A two-step
1. First jump the two points to the same floor , In fact, let the deeper point jump to the same level as the shallower point , Here is the x Jump to and y Same floor

Based on the idea of a binary patchwork , For example, it has been pretreated 2 Of k Number to the power , Want to come up with t, Just take a look t The binary representation of , Then gather together , Just look directly from small to large , as long as t Greater than 2 The current order of , Just explain t Is to include this one , Then compare while reducing

then , Applied to the lca It's inside ,x To jump to y, What needs to jump is depth[y] - depth[x] Step , Then it has been pretreated f[i][j] Just enumerate from large to small , It's good to round up this number. In fact, you don't have to round up this number , Only need to enumerate , As long as meet

This condition can jump up
2. Let the two points jump up at the same time （ If the same point is reached after the first step , You can just end , There is no need for the second step ）, Until both are the next level of common ancestors , The reason why we don't jump directly to the public ancestor is for the convenience of judgment

If f[a][k] = f[b][k] Words , We can only say f[a][k] and f[b][k] yes a and b A common ancestor of , It can't be said to be the recent public ancestor , But if f[a][k] != f[b][k] Words , Means f[a][k] = f[b][k] Not yet on the common ancestor , Because of this , Let's jump to the next point of the common ancestor , If equal , It is impossible to judge whether this point is the nearest public ancestor , Because it may also be the upper point of the nearest common ancestor , This cannot be judged

When jumping, it is also based on the idea of binary patchwork , Enumerate from big to small k, In the process of enumeration , As long as we jump $2^K$ After step f[a][k] != f[b][k], It means they haven't jumped to their proper position , Just haven't jumped to the nearest public ancestor , You can let them jump up together once , until k Enumerate until , After enumeration x and y Even if we go to the next level of public ancestors , Now , Their common ancestor should be from x perhaps y Jump up one step

The time complexity of these two steps is logn, The preprocessing time complexity is nlogn Of , This multiplication requires lca Is also the most commonly used way

In the actual process , There will also be sentinels

be based on RMQ How to do it

First, put the whole tree dfs Go through it , Record in the process of traversal dfs Sequence , The time of recording here is every time we traverse , Whether it is backtracking or the first traversal, you should record , The following is an example

dfs The sequence should be

Here or here x and y Distance between , That's a 8 One 5, Any one 8 One 5 Fine , Then it turns into the interval minimum problem , You can use it RMQ Or segment tree

Example

Grandson asked

The board question is not explained

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 40010;
vector<int> v[N];
int depth[N], fa[N][16];
queue<int> q;
int root, n, m;

void bfs()
{
    
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0; depth[root] = 1;
	q.push(root);
	while(q.size())
	{
    
		int t = q.front();
		q.pop();
		for(auto i : v[t])
		{
    
			if(depth[i] > depth[t] + 1)
			{
    
				depth[i] = depth[t] + 1;
				q.push(i);
				fa[i][0] = t;
				for(int j=1; j<=15; j ++)
				{
    
					fa[i][j] = fa[fa[i][j - 1]][j - 1];
				}
			}
		}
	}
	
}

int lca(int a, int b)
{
    
	if(depth[a] < depth[b]) swap(a, b);
	for(int i=15; i>=0; i--)
		if(depth[fa[a][i]] >= depth[b])
			a = fa[a][i];
	if(a == b) return a;
	
	for(int i=15; i>=0; i--)
		if(fa[a][i] != fa[b][i])
		{
    
			a = fa[a][i];
			b = fa[b][i];
		}
	
	return fa[a][0];
	
}

signed main()
{
    
	fast;
	cin >> n;
	int a, b;
	for(int i=1; i<=n; i++)
	{
    
		cin >> a >> b;
		if(b == -1) root = a;
		else
		{
    
			v[a].push_back(b);
			v[b].push_back(a);
		}
	}
	
	bfs();
	
	cin >> m;
	while(m --)
	{
    
		cin >> a >> b;
		int p = lca(a, b);
		if(p == a) puts("1");
		else if(p == b) puts("2");
		else puts("0");
	}
	
	return 0;
}