最近公共祖先离线做法（tarjan）

在线离线

在线和离线一般是针对有询问的题目

在线做法：就是每读入一个询问，就可以立即算一个答案，然后输出

离线做法：我们必须先把所有询问统一读进来，然后统一计算完之后，再把所有询问统一输出

tarjan O(n + m)

n是节点数量，m是询问数量
本质是对向上标记法的优化

向上标记法

具体可看上一个在线做法

在深度优先遍历过程中把所有点分为三大类
1.已经遍历过，且回溯过的点，被搜过，而且子树被搜完
2.正在搜索的分支
3.还未搜索到的点

假设是从左往右搜索，就形成了这样的一棵树绿色是第一种，红色是第二种，也就是一个路径，其他的是第三种

对于正在搜索的点，我们找一下与之相关的询问，由上图可以发现，当前询问的点x和绿色部分的公共祖先都是路径总的点，因为可以将路径中点的子树合并到该点中去，最后求公共祖先的时候，就是看一下那个点被合并到哪个点去了，可以用并查集来实现，这就是找祖宗节点

这样，每个点只会被遍历一次，也只会被合并一次，对于每个查询也只会查询一次

主要思想

我们在遍历当前这个分支的时候，对于所有和这个点相关的节点的公共祖先，我们可以发现，如果这个点已经被遍历过了的话，所在整个子树的公共祖先都是路径中的那个点，也就是该子树的根节点，也就是每次遍历完一个点之后，就可以把当前这个点直接合并到根节点当中去，当我们查询的时候，就可以直接在并查集里面查当前元素的代表元素是谁，这个代表元素就是它的公共祖先

这个要注意什么时候合并，就是要在回溯完之后，再把它合并到父节点中

例题

距离
题意就是要求两个点之间的距离

方法如图，都算出来到根节点的距离，再减去两倍的公共祖先的距离

#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];//存储每个点到根节点距离 
int p[N];
int res[N * 2];// 存答案 
int st[N];
vector<PII> query[N];   // first存查询的另外一个点，second存查询编号
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)//查看另一个点是不是回溯过了，如果没回溯过就跳 
		{
    
			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;
}