Graph theory (nearest common ancestor LCA)

One 、 Basics

1、 Definition ： On a rooted tree , For a node z, both x The ancestors of the , It's also y The ancestors of the , that z yes x,y The common ancestor of , If z stay x,y The deepest of all the common ancestors of , We call it the nearest common ancestor , remember z = LCA(x,y)

2、 Violence seeks （ Worst time complexity O(n)）：

（1）、 from x Go up to the root node , And mark the passing nodes , Then make y Go up to the root node , When you first encounter a marked point , I found it LCA(x,y)

（2）、 Make x,y Go up to the deeper point in the x,y Isobath , Then you can access up at the same time , Until the same node is accessed , This node is LCA(x,y)

Two 、 Tree multiplication method for LCA（ On-line ）

The multiplication method is used to find LCA= Tree multiplication + Violence seeks a second way

1、 The doubled part of a tree dp surface ：

① set up dp[x][k] Express x Of 2^k Generations of ancestors , That is, go to the root node 2^k Step to the node

② If such a node does not exist, then dp[x][k] = 0, that dp[x][0] On behalf of x Parent node

③ besides , about k∈[1, log n], Yes dp[x][k] = dp[dp[x][k - 1]][k - 1], representative x Of 2^k Generations of ancestors are equal to x Of 2^(k - 1) Of our ancestors 2^(k - 1) Generations of ancestors

We can traverse the tree , Calculate each point at a time dp The values in the array , By the way, the depth of the node in the tree

2、 utilize dp Array to find LCA

① Make deep[x]>=deep[y], The idea of binary splitting , hold x Adjust up to and y At the same depth . say concretely , Namely x Try to walk up k=2^log n、……、2^1、2^0 Step , Check whether the arriving node is smaller than y deep , Then order x=dp[x][k], If at this time x = y, be LCA(x,y)=x

② Using binary splitting idea , hold x,y Adjust upward at the same time , Keep the same depth , And the two do not meet . say concretely , Is trying to go up k = 2^log n、……、2^1、2^0 Step , If dp[x][k] ≠ dp[y][k], Then order x = dp[x][k],y = dp[y][k] here x,y It must be a one-step meeting , Their parent node dp[x][0] Namely LCA(x,y)

3、 Code implementation

int to[maxn << 1], nex[maxn << 1], head[maxn];
int dp[maxn][32], deep[maxn], dis[maxn];
int cnt, nn, n, m, r;
void add(int u, int v)
{
	to[++cnt] = v;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void bfs(int root)
{
	queue<int>q;
	q.push(root);
	deep[root] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = nex[i])
		{
			int v = to[i];
			if (deep[v])
				continue;
			deep[v] = deep[u] + 1;
			dp[v][0] = u;
			for (int j = 1; j <= nn; j++)
				dp[v][j] = dp[dp[v][j - 1]][j - 1];
			q.push(v);
		}
	}
}
void dfs(int x)
{
	for (int i = 1; i <= nn; i++)
		dp[x][i] = dp[dp[x][i - 1]][i - 1];


	for (int i = head[x]; i; i = nex[i])
	{
		int y = to[i];
		if (deep[y])
			continue;
		deep[y] = deep[x] + 1;
		dp[y][0] = x;
		dfs(y);
	}
	return;
}
int lca(int u, int v)
{
	if (deep[u] > deep[v])
		swap(u, v);
	for (int i = nn; i >= 0; i--)
	{
		if (deep[dp[v][i]] >= deep[u])
			v = dp[v][i];
	}
	if (u == v)
		return u;
	for (int i = nn; i >= 0; i--)
	{
		if (dp[u][i] != dp[v][i])
		{
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[u][0];
}
void solve()
{
	cin >> n >> m >> r;
	nn = (int)(log(n) / log(2)) + 1;
	for (int i = 1; i <= n; i++)
		head[i] = deep[i] = 0;
	cnt = 0;

	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	deep[r] = 1;
	dfs(r);
    //bfs(r);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		cout << lca(u, v) << '\n';
	}
}

3、 ... and 、Tarjan seek LCA（ offline ）

1、 At any time of depth first traversal , There are three kinds of points ：

① The nodes that have been visited and traced , That is, all the child nodes have been accessed , These nodes are marked as 2

② Nodes that have started recursion but have not yet backtracked , These nodes are the nodes being accessed x as well as x Parent node , These nodes are marked as 1

③ Nodes that have not been accessed , Marked as 0

2、 For the node being accessed x, Its path to the root node has been marked 1, If at this time y Is the node that has been visited and traced （ The table is marked as 2）, From y Go up to the root , The first encountered tag is 1 The point is LCA(x,y)

3、 And look up set optimization ：

When a node gets an integer 2 When you mark , Merge its set into the set of its parent node , At this point, its parent node must be marked as 1, And form a set separately .

This is equivalent to that every node that completes backtracking has a pointer to its parent node , Just check y The representative elements of the set in which they are located , namely find operation , Is equivalent to from y Go up to a node that starts recursion but does not complete backtracking , namely LCA(x,y)

4、 Scan and x All relevant inquiries , If you ask one of the points y The mark of is 2, that LCA(x,y) Namely find(y)

5、 Code implementation

int to[maxn << 1], nex[maxn << 1], head[maxn];
int fa[maxn], vis[maxn], ans[maxn];
vector<int>query[maxn], queryid[maxn];
int cnt, n, m, r;
void add(int u, int v)
{
	to[++cnt] = v;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void addquery(int u, int v, int id)
{
	query[u].push_back(v);
	query[v].push_back(u);
	queryid[u].push_back(id);
	queryid[v].push_back(id);
}
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void tarjan(int u)
{
	vis[u] = 1;
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (vis[v])
			continue;
		tarjan(v);
		fa[v] = u;
	}
	for (int i = 0; i < query[u].size(); i++)
	{
		int v = query[u][i], id = queryid[u][i];
		if (vis[v] == 2)
			ans[id] = find(v);
	}
	vis[u] = 2;
}
void solve()
{
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		if (u == v)
			ans[i] = u;
		else
			addquery(u, v, i);
	}
	tarjan(r);
	for (int i = 0; i < m; i++)
	{
		cout << ans[i] << '\n';
	}
}