Recent public ancestor offline practice (tarjan)

Online and offline

Online and offline are generally for questions that are asked

Online practice ： Every time I read a question , You can calculate an answer immediately , Then the output

Offline approach ： We must first read all the questions in a unified way , Then after unified calculation , Then output all queries in a unified way

tarjan O(n + m)

n It's the number of nodes ,m Is the number of inquiries
The essence is to optimize the upward marking method

Upward marking method

See an online practice for details

In the depth first traversal process, all points are divided into three categories
1. It's been traversed , And back to the point , Searched , And the subtree was searched
2. Branch being searched
3. Points that have not been searched

Suppose you search from left to right , It forms such a tree. Green is the first , Red is the second , That is, a path , The others are the third

For the point being searched , Let's look for related questions , You can see from the picture above , Current inquiry point x And the common ancestor of the green part are the general points of the path , Because the subtree at the midpoint of the path can be merged into that point , Finally, when we seek common ancestors , Just look at the point to which that point is merged , It can be realized by combining and searching sets , This is to find the ancestor node

such , Each point will be traversed only once , It will only be merged once , For each query, it will only be queried once

The main idea

When we traverse the current branch , For the common ancestor of all nodes related to this point , We can find out , If this point has been traversed , The common ancestor of the whole subtree is the point in the path , That is, the root node of the subtree , That is, after traversing a point every time , You can merge the current point directly into the root node , When we look up , You can directly check who is the representative element of the current element in the parallel search set , This representative element is its common ancestor

Pay attention to when to merge , That is, after the backtracking , Then merge it into the parent node

Example

distance
The meaning of the question is to ask for the distance between two points

The method is shown in the figure , Calculate the distance to the root node , Subtract twice the distance of the common ancestor

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define PII pair<int, int>
const int N = 1e4 + 10;
#define x first
#define y second
vector<PII> v[N];
int n, m, a, b, k;
int dist[N];// Store the distance from each point to the root node  
int p[N];
int res[N * 2];//  Save the answer  
int st[N];
vector<PII> query[N];   // first Another query save point ,second Save query number 
int find(int x)
{
    
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u, int fa)
{
    
	for(auto i : v[u])
	{
    
		if(i.x == fa) continue;
		dist[i.x] = dist[u] + i.y;
		dfs(i.x, u);
	}
}

void tarjan(int u)
{
    
	st[u] = 1;
	for(auto i : v[u])
	{
    
		if(!st[i.x])
		{
    
			tarjan(i.x);
			p[i.x] = u;
		}
	}
	
	for(auto i : query[u])
	{
    
		if(st[i.x] == 2)// Check whether another point has been traced , If you haven't looked back, jump  
		{
    
			int anc = find(i.x);
			res[i.y] = dist[u] + dist[i.x] - dist[anc] * 2;
		}
	}
	st[u] = 2;
}

signed main()
{
    
	cin >> n >> m;
	for(int i=1; i<=n-1; i++)
	{
    
		cin >> a >> b >> k;
		v[a].push_back({
    b, k});
		v[b].push_back({
    a, k});
	}
	
	for(int i=1; i<=m; i++)
	{
    
		cin >> a >> b;
		if(a != b)
		{
    
			query[a].push_back({
    b, i});
			query[b].push_back({
    a, i});
		}
	}
	for(int i=1; i<=n; i++) p[i] = i;
	
	dfs(1, -1);
	
	tarjan(1);
	
	for(int i=1; i<=m; i++) cout << res[i] << endl; 
	return 0;
}