Tree Difference and LCA

You can see this video from station b Very nice and highly recommended

LCA

What is LCA

Least Common Ancester, the full name of the LCA, is the latest common ancestor

• Ancestor: The point that passes through the path from the root of the tree to the current node (excluding the current node, and because it is a tree, the path is unique)
• Common Ancestor: The point at which the ancestors of two nodes intersect
• Recent Common Ancestor: The deepest of the common ancestors of two nodes

How to solve LCA?

First consider two points of the same depth
For two points with the same depth x,y their depth difference to LCA is the same
So we can take x,y and jump up at the same time until we jump to the same node. But this is inefficient and may get stuck as O(N).

Consider using multiplication to optimize
Assuming the distance from LCA to x is d, d must be represented as a binary number
Just assign 0/1 to each bit of this binary tree and find the smallest d, which is equivalent to having the node jump every time 2 k 2^k 2k steps

How to make a node jump every time 2 k 2^k 2k steps?
We can double-record the ancestors of the current node so that f a [ i ] [ j ] fa[i][j] fa[i][j] representation i i i On 2 j 2^j Who is the ancestor of Level 2j? Recursive
f a [ i ] [ j ] = f a [ f a [ i ] [ j − 1 ] ] [ j − 1 ] fa[i][j]=fa[fa[i][j-1]][j-1] fa[i][j]=fa[fa[i][j−1]][j−1]
spot i Of No. 2 j layer Ancestor before ， yes spot i Of 2 j − 1 layer Ancestor before again to upper jump 2 j − 1 layer The 2nd ^j ancestor of point i is the 2nd ^{j-1} ancestor of point i and jumps up the 2nd ^{j-1} layer The 2J ancestor of point i is the 2j_1 ancestor of point i and jumps up 2j_1 layer
So we just need to calculate the minimum depth d for the node to jump up
We enumerate from large to small when we calculate binary numbers, so we also enumerate j from large to small

If f a [ x ] [ j ] = = f a [ y ] [ j ] fa[x][j]==fa[y][j] fa[x][j]==fa[y][j], it's possible to skip the LCA without jumping
If f a [ x ] [ j ] ! = f a [ y ] [ j ] fa[x][j]!=fa[y][j] fa[x][j]!=fa[y][j], jump up without skipping LCA
If f a [ x ] [ j ] = = f a [ y ] [ j ] fa[x][j]==fa[y][j] fa[x][j]==fa[y][j], maybe it's the LCA, but we didn't jump up, then we can just go back to the father node, because we will eventually jump up again

for(int j=20;j>=0;j--){
	if(fa[x][j]!=fa[y][j]){
		x=fa[x][j],y=fa[y][j];
	}
	return fa[x][0]
}

So what if the depths are different?
Let's just let the deep nodes jump to the same depth as the deep nodes, and still use the doubling like doubling method, each time 2 j 2^j 2j. (It's just splitting binaries.)

int LCA(int x,int y){
	if(deep[x]>deep[y])swap(x,y);//Make deep[x]<deep[y]
	for(int i=t;i>=0;i--)
		if(deep[fa[y][i]]>=deep[x])y=fa[y][i];//Set x to the same depth as y
	if(x==y)return x;
	for(int i=t;i>=0;i--)//Let x and y go up 2^i steps at the same time
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
		}
	return fa[x][0];
}

Build a tree before doing LCA and use dfs or bfs to find out the depth of each point and the parent node

Example

Logu P3379 (Template) Recent Common Ancestor (LCA)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
#define endl '\n'
//CHECK MULTIPLY INPUT	!!!
//NEW DATA CLEAN	!!!
//THINK > CODE	!!!
const int N=5e5+10,M=25;
int fath[N][M],dep[N];
vector<int>root[N];
int n,m,s;
void dfs(int u,int fa){
	fath[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(auto v:root[u]){
		if(v!=fa)dfs(v,u);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
		x=fath[x][(int)log2(dep[x]-dep[y])];
	if(x==y)return y;
	for(int i=20;i>=0;i--){
		if(fath[x][i]!=fath[y][i]){
			x=fath[x][i],y=fath[y][i];
		}
	}
	if(fath[x][0]==0)return s;
	return fath[x][0];
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		root[x].push_back(y);
		root[y].push_back(x);
	}
	dfs(s,0);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			fath[i][j]=fath[fath[i][j-1]][j-1];
	while(m--){
		int x,y;cin>>x>>y;
		cout<<LCA(x,y)<<endl;
	}
	return 0;
}

Tree Difference

Point difference

Solve the problem: Add a value to all the points on the path, and weigh each point.

We split the path into x-LCA,y-LCA
Every part goes up from bottom
For the x-LCA section, we only need m a r k [ x ] + + , m a r k [ f a [ L C A ] [ 0 ] ] − − mark[x]++,mark[fa[LCA][0]]-- mark[x]++,mark[fa[LCA][0]]−−
For the y-LCA section, we only need m a r k [ y ] + + , m a r k [ f a [ L C A ] [ 0 ] ] − − mark[y]++,mark[fa[LCA][0]]-- mark[y]++,mark[fa[LCA][0]]−−
Then we found that the LCA has been modified twice, so we want to remove a duplicate differential marker from the LCA
m a r k [ L C A ] − − , m a r k [ f a [ L C A ] [ 0 ] ] + + mark[LCA]--,mark[fa[LCA][0]]++ mark[LCA]−−,mark[fa[LCA][0]]++

To sum up

int lca=LCA(x,y);
mark[x]++,mark[y]++;
mark[lca]--,mark[fa[lca][0]]--;

The last weight of each point is the sum of the mark values of its subtrees

Difference by Edge

Solve the problem by adding a value to each edge of the x-y path and finding the value of each edge

Common method: edge-weighted point power (edge-weighted delegation)
Each node has at most one parent, that is, only one edge connected up
So we convert the edge weight of an edge into the point weight of a child node (the root node has no point weight)
This translates into point differences
For x-y paths, they are also divided into x-LCA and y-LCA
Note, however, that the weight of the LCA does not change

mark[x]++,mark[y]++,mark[LCA]-=2

Finally, the weight of each point is the sum of the mark values of its subtree, and then the edge weight can be turned back (record the corresponding edge of each point during preprocessing).

Differential by Depth

Solve the problem: In the subtree of x, modify the point whose depth is dep[x]~dep[x]+k

Make a note of the changes made to X. When you search for x, mark the changes differently for each change.
Note that if k is very large, change to <=n
Finally remember to go back
The process is as follows: Record modifications - Deep search nodes - Mark differences - Prefix and calculate answers - Backtrace returns the differences

CF1076E

Insert a code snippet here