问题描述:
给定一棵有根多叉树，求出指定两个点直接最近的公共祖先
| 输入：第 1 行输入 3 个正整数 N、M、S，分别表示树的节点个数、查询的个数、树根节点的序号。接下来 N – 1 行中，每行输入两个正整数。x 和 y，表示节点 x 和节点 y 之间有一条直连的边（数据保证可以构成树）。接下来 M 行中，每行输入两个正整数 a 和 b，表示查询节点 a 和节点的最近公共祖先。 |
| 输出：输出 M 行，每行包含一个正整数，表示每个查询的结果 |
| 数据范围：N ≤ 500000，M ≤ 500000。 |
| 输入样例 | 输出样例 |
| 5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 | 4 4 1 4 4 |
倍增法求LCA
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
struct Edge{int to, next;}edge[2*N]; //链式前向星
int head[2*N], cnt;
void init(){ //链式前向星：初始化
for(int i=0;i<2*N;++i){ edge[i].next = -1; head[i] = -1; } //head[]储存关联的节点，有重复输入的节点，就将旧的关联节点放到next，再更新新的节点
cnt = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
} //以上是链式前向星
int fa[N][20], deep[N];
void dfs(int x,int father){ //求x的深度deep[x]和fa[x][]。father是x的父结点。
deep[x] = deep[father]+1; //深度：比父结点深度多1
fa[x][0] = father; //记录父结点
for(int i=1; (1<<i) <= deep[x]; i++) //求fa[][]数组，它最多到根结点
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int i=head[x]; ~i; i=edge[i].next) //遍历结点i的所有孩子。~i可写为i!=-1
if(edge[i].to != father) //邻居：除了父亲，都是孩子
dfs(edge[i].to, x);
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y); //让x位于更底层，即x的深度值更大
//（1）把x和y提到相同的深度
for(int i=19;i>=0;i--) //x最多跳19次：2^19 > 500005
if(deep[x]-(1<<i)>=deep[y]) //如果x跳过头了就换个小的i重跳
x = fa[x][i]; //如果x还没跳到y的层，就更新x继续跳
if(x==y) return x; //y就是x的祖先
//（2）x和y同步往上跳，找到LCA
for(int i=19;i>=0;i--) //如果祖先相等，说明跳过头了，换个小的i重跳
if(fa[x][i]!=fa[y][i]){ //如果祖先不等，就更新x、y继续跳
x = fa[x][i]; y = fa[y][i];
}
return fa[x][0]; //最后x位于LCA的下一层，父结点fa[x][0]就是LCA
}
int main(){
init(); //初始化链式前向星
int n,m,root; scanf("%d%d%d",&n,&m,&root); //树的节点个数、查询的个数、树根节点的序号
for(int i=1;i<n;i++){ //读一棵树，用链式前向星存储
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs(root,0); //计算每个结点的深度并预处理fa[][]数组
while(m--){
int a,b; scanf("%d%d",&a,&b);
printf("%d\n", LCA(a,b));
}
return 0;
}
笔记：用倍增法求LCA，是利用二进制的倍增，先将x，y提到统一深度，判断是不是同一根链子上的，如果是返回x，如果不是就用倍增法逼近最近的公共祖先
Tarjan求LCA
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int fa[N], head[N], cnt, head_query[N], cnt_query, ans[N];
bool vis[N];
struct Edge{ int to, next, num;}edge[2*N], query[2*N]; //链式前向星
void init(){ //链式前向星：初始化
for(int i=0;i<2*N;++i){
edge[i].next = -1; head[i] = -1;
query[i].next = -1; head_query[i] = -1;
}
cnt = 0; cnt_query = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void add_query(int x, int y, int num) { //num 第几个查询：
query[cnt_query].to = y;
query[cnt_query].num = num; //第几个查询
query[cnt_query].next = head_query[x]; //记录上一个的相同节点的序号
head_query[x] = cnt_query++; //更新节点序号
}
int find_set(int x) { //并查集查询
return fa[x] == x ? x : find_set(fa[x]);
}
void tarjan(int x){ // tarjan是一个DFS
vis[x] = true; //记录已经遍历过
for(int i=head[x]; ~i; i=edge[i].next){ // ~i可以写为i!=-1
int y = edge[i].to;
if( !vis[y] ) { //遍历子结点
tarjan(y);
fa[y] = x; //合并并查集：把子结点y合并到父结点x上
}
}
for(int i = head_query[x]; ~i; i = query[i].next){ //查询所有和x有询问关系的y
int y = query[i].to;
if( vis[y]) //如果to被访问过
ans[query[i].num] = find_set(y); //LCA就是find(y)
}
}
int main () {
init();
memset(vis, 0, sizeof(vis)); //初始化
int n,m,root; scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){ //读n个结点
fa[i] = i; //并查集初始化
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u); //存边
}
fa[n] = n; //并查集的结点n
for(int i = 1; i <= m; ++i) { //读m个询问
int a, b; scanf("%d%d",&a,&b);
add_query(a, b, i); add_query(b, a, i); //存查询
}
tarjan(root);
for(int i = 1; i <= m; ++i) printf("%d\n",ans[i]);
}
笔记：两个链式向前星分别储存树节点和离线查询。DFS从树叶开始向上查询最近的公共祖先，如果查询里的另一个节点没有遍历到会跳过，继续寻找该节点的里的另一组查询，或者继续DFS查询另一个节点
树链剖分的概念与LCA
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
struct Edge{int to, next;}edge[2*N]; //链式前向星
int head[2*N], cnt;
void init(){ //链式前向星：初始化
for(int i=0;i<2*N;++i){ edge[i].next = -1; head[i] = -1; }
cnt = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; //链式前向星
}
int deep[N],siz[N],son[N],top[N],fa[N]; //深度、子树大小、非叶子结点的重儿子、链头、父节点
void dfs1(int x, int father){
deep[x]=deep[father]+1; //深度：比父结点深度多1
fa[x]=father; //标记x的父亲
siz[x]=1; //标记每个结点的子树大小（包括自己）
for(int i=head[x];~i;i=edge[i].next){
int y=edge[i].to;
if(y!=father){ //邻居：除了父亲，都是孩子
fa[y]=x;
dfs1(y,x);
siz[x] += siz[y]; //回溯后，把x的儿子数加到x身上
if(!son[x] || siz[son[x]]<siz[y]) //标记每个非叶子结点的重儿子
son[x]=y; //x的重儿子是y
}
}
}
void dfs2(int x,int topx){
top[x] = topx; //x所在链的链头
if(!son[x]) return; //x是叶子，没有儿子，返回
dfs2(son[x],topx); //先dfs重儿子，所有重儿子的链头都是topx
for(int i=head[x];~i;i=edge[i].next){ //再dfs轻儿子
int y=edge[i].to;
if(y!=fa[x] && y!=son[x])
dfs2(y,y); //每一个轻儿子都有一条以它为链头的重链
}
}
int LCA(int x, int y){
while(top[x]!=top[y]){ //持续往上跳，直到若x和y属于同一条重链
if(deep[top[x]] < deep[top[y]]) swap(x,y); //让x是链头更深的重链
x = fa[top[x]]; //x穿过轻边，跳到上一条重链
}
return deep[x]<deep[y] ? x : y;
}
int main(){
init();
int n,m,root; scanf("%d%d%d",&n,&m,&root); //节点个数、询问的个数和树根结点
for(int i=1;i<n;i++){ //输入多叉树
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs1(root,0);
dfs2(root,root);
while(m--){
int a,b; scanf("%d%d",&a,&b); //在线查询
printf("%d\n", LCA(a,b)); //返回
}
}
笔记：重链剖分是把子节点最大的儿子称为重儿子，把树分为若干条重链。把树刨分成链后，每次查询LCA直接指向链头，可以实现更快速度的“跳跃”
LCT的基本应用
#include<bits/stdc++.h>
using namespace std;
const int N=500000+5;
/* fa表示父节点的索引。
* ch[2]表示左右子节点的索引。
* sum表示从根节点到当前节点路径上的异或和。
* val表示当前节点的值。
* lazy用于标记是否需要对当前节点及其子树进行翻转操作。*/
struct node{ int fa,ch[2],sum,val,lazy; }t[N];
#define lc t[x].ch[0] //左儿子
#define rc t[x].ch[1] //右儿子
bool isRoot(int x){ //判断是否是splay根节点
int g=t[x].fa; //通过检查节点x在其父节点g中的位置
return t[g].ch[0]!=x && t[g].ch[1]!=x; //若为根,则父结点不应该有这个儿子
}
void pushup(int x){ //维护从根节点到节点x路径上的异或和，题目要求
t[x].sum=t[x].val^t[lc].sum^t[rc].sum; //更新节点x的sum值，使其等于节点x自身值与左右子节点sum值的异或运算结果。
}
void reverse(int x){ //翻转节点x的左右子树，并更新lazy标记
if(!x)return;
swap(lc,rc); //翻转x的左右儿子
t[x].lazy^=1; //懒惰标记，先不翻转儿子的后代，后面再翻转
}
void pushdown(int x){ //递归翻转x的儿子的后代，并释放懒标记。
if(t[x].lazy){ //若节点x的lazy标记位为1，表明节点的子树需要进行翻转。
reverse(lc); //函数递归地对节点x的左右子节点进行翻转
reverse(rc);
t[x].lazy=0; //清零节点x的lazy标记位，表示已处理完翻转操作
}
}
void push(int x){ //将节点x及其祖先节点的lazy标记传递到根节点，并更新lazy标记
if(!isRoot(x)) push(t[x].fa); //从根到x全部pushdown
pushdown(x);//
}
void rotate(int x){ //节点的旋转操作，保持二叉树的平衡
int y=t[x].fa; //获取当前节点x的父节点y,和父节点y的父节点z
int z=t[y].fa;
int k=t[y].ch[1]==x; //确定节点x是在父节点y的左子树还是右子树
if(!isRoot(y)) t[z].ch[t[z].ch[1]==y]=x; //如果节点y不是根节点，则更新节点z的子节点指向
t[x].fa=z; //更新节点x的父节点为节点z，（认父不认子）
t[y].ch[k]=t[x].ch[k^1]; //更新节点y的子节点，k^1表示取反，x的子节点赋值给y的子节点
if( t[x].ch[k^1] ) t[ t[x].ch[k^1] ].fa = y; //如果节点x的k子节点存在，k子节点的父节点设为y
t[y].fa=x; //更新节点y的父节点为节点x
t[x].ch[k^1]=y; //更新节点x的子节点，完成旋转
pushup(y); //更新旋转后节点y的值，保持树的属性
}
void splay(int x){ //将节点x旋转为它所在的Splay树的根节点
int y,z;
push(x); //处理x的所有子孙的lazy标记
while(!isRoot(x)){ //在循环中不断进行旋转操作，直至节点x成为Splay树的根节点
y=t[x].fa,z=t[y].fa; //获取节点x的父节点y，和父节点y的父节点z
if(!isRoot(y)) //如果节点y不是根节点，则执行旋转操作
(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y); //如果节点y是z的左儿子，则执行左旋操作，否则执行右旋操作
rotate(x);
}
pushup(x); //更新节点x的sum值
}
void access(int x){ //从x往上走，沿着虚边走到根，过程中通过splay将访问的节点旋转到根节点，并建立实链
for(int child=0; x; child=x, x=t[x].fa){ //从节点x开始，沿父节点向上遍历至根节点
splay(x); //将节点x旋转到根节点
rc = child; //将右孩子设置为child，建立一条实边
pushup(x); //更新节点x及其父节点的信息
}
}
void makeroot(int x){ //将节点x旋转到原树的根节点位置
access(x); //在原树上建立到节点x的实链
splay(x); //节点x成为Splay树根
reverse(x); //翻转节点x的子树
}
void link(int x,int y){ //在结点x和y之间连接一条边
makeroot(x); //将节点x旋转到原树的根节点位置
t[x].fa=y; //节点x的父节点设置为节点y
}
int query_lca(int x, int y) { //求LCA(x, y)
access(x);
int ans;
for (int child = 0; y; child = y, y = t[y].fa) { //模拟access(), y==0时退出
splay(y); //若y在从根出发的路径p上，splay(y)后y是Splay的根，y没有父结点，t[y].fa=0
t[y].ch[1] = child;
ans = y;
}
return ans;
}
int main() {
int n,m,rt; scanf("%d%d%d",&n,&m,&rt);
for (int i=1; i<n; ++i) { int x,y; scanf("%d%d",&x,&y); link(x, y);}
makeroot(rt); //定义根结点是rt
for (int i=1; i<=m; ++i){ int x,y; scanf("%d%d",&x,&y); printf("%d\n", query_lca(x, y));}
return 0;
}
笔记：大部分代码跟动态树的一样，用LTC解决LCA问题需要使用access(x)函数，先用x建立一条从根到x的实链，实链上的节点必然有一个是LCA，然后y节点在执行access的过程会向着树根走，肯定会遇到一个实链的节点，那这个节点就是LCA