洛谷 P3379：最近公共祖先（LCA）← 树链剖分 + 链式前向星

【题目来源】 https://www.luogu.com.cn/problem/P3379 【题目描述】 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 【输入格式】 第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N−1 行每行包含两个正整数 x,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 M 行每行包含两个正整数 a,b，表示询问 a 结点和 b 结点的最近公共祖先。 【输出格式】 输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。 【输入样例】 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 【说明/提示】 对于 30% 的数据，N≤10，M≤10。 对于 70% 的数据，N≤10000，M≤10000。 对于 100% 的数据，1≤N,M≤500000，1≤x,y,a,b≤N，不保证 a≠b。 【算法分析】 ● 树链剖分（Heavy-Light Decomposition，HLD）是一种将树结构转化为线性序列的算法技巧，常用于解决树上路径查询与修改‌以及‌子树查询与修改‌这两大类问题。 其主要包括两个分解步骤： （1）重链剖分‌：将树的边分为“重边”和“轻边”。对于每个非叶子节点，选择其所有子节点中‌子树大小最大‌的那一个，连接这两点的边即为重边，连接到其他子节点的边则为轻边。由重边相连形成的路径称为重链。 （2）DFS 序重排‌：通过一次深度优先搜索，优先遍历重儿子，从而保证‌每条重链上的节点在新的 DFS 序中是连续存储的‌。 ● 树链剖分的核心思想是通过两次 DFS 对树进行剖分，将树分解为若干条“重链”，并重新安排节点的访问顺序（DFS 序），使得每条重链上的节点在序列中连续存储，同时每个子树内的节点也连续存储。这样，复杂的树形操作就被转化为了对线性序列的区间操作，可以借助线段树、树状数组等数据结构高效地完成。 ● 树链剖分的几个重要概念 （1）重儿子 (Heavy Son)‌：对于树中的一个非叶子节点，其所有子节点中，‌子树大小（含子树的根的节点数）最大‌的那个子节点，称为该节点的重儿子。如果存在多个子节点子树大小相同，可任意选取其中一个作为重儿子。 （2）轻儿子 (Light Son)‌：非叶子节点的所有子节点中，除了重儿子以外的其他子节点，都称为该节点的轻儿子。 （3）重边 (Heavy Edge)‌：连接一个节点与其重儿子的边，称为重边。 （4）轻边 (Light Edge)‌：连接一个节点与其轻儿子的边，称为轻边。 （5）重链 (Heavy Path)‌：由一系列连续的重边首尾相连形成的路径，称为一条重链。整棵树可以被分解为若干条互不相交的重链。 （6）链头 (Head of Chain / Top)‌：每条重链的起始节点，即这条链上‌深度最浅‌的那个节点，称为该重链的链头。树根通常单独构成一条重链，其本身即为链头。 ● 树链剖分的两个 dfs 函数 （1）dfs1 函数。求解数组 dep[]、pre[]、son[]、siz[] int dep[N]; //dep[x] represents depth of node x int pre[N]; //pre[x] represents parent node of node x int son[N]; //son[x] represents heavy child of non-leaf node x int siz[N]; //siz[x] represents number of nodes in the subtree rooted at node x （2）dfs2 函数。求解数组 top[] int top[N]; //top[x] represents head node of the heavy chain where node x is located ● 链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904 大佬 yxc 指出“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中： e[idx]：存储序号为 idx 的边的终点值 ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）‌ h[a]：存储头结点 a 指向的边的序号 val[idx]：存储序号为 idx 的边的权值（可选） 【算法代码一：含注释版】

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int h[N],e[N<<1],ne[N<<1],idx;
int dep[N]; //dep[x] represents depth of node x
int pre[N]; //pre[x] represents parent node of node x
int son[N]; //son[x] represents heavy child of non-leaf node x
int siz[N]; //siz[x] represents number of nodes in the subtree rooted at node x
int top[N]; //top[x] represents head node of the heavy chain where node x is located

void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs1(int u,int fa) { //Solving for dep[],pre[],son[],siz[]
dep[u]=dep[fa]+1;
pre[u]=fa;
siz[u]=1; //Mark the size of the subtree (including itself) for each node
for(int i=h[u]; i!=-1; i=ne[i]) {
int j=e[i];
if(j!=fa) {
pre[j]=u;
dfs1(j,u);
siz[u]+=siz[j]; //add the number of u's sons to u himself
if(!son[u] || siz[son[u]]<siz[j]) { //Mark eavy children of each non-leaf node
son[u]=j; //u's heavy son is j
}
}
}
}

void dfs2(int x,int topx) { //Solving for top[]
top[x]=topx; //top[x] represents head of heavy chain where x is located
if(!son[x]) return; //If x is a leaf node, return

//perform dfs2 on the heavy children
//All the head nodes of the chains of the heavy children are topx
dfs2(son[x],topx);

for(int i=h[x]; i!=-1; i=ne[i]) { //perform dfs2 on the thin children
int j=e[i];
if(j!=pre[x] && j!=son[x]) {
dfs2(j,j); //Each light son has a heavy chain attached to itself as the chainhead.
}
}
}

int LCA(int x, int y) {
while(top[x]!=top[y]) { //Keep jumping until x and y belong to the same heavy chain
if(dep[top[x]]<dep[top[y]]) {
swap(x,y);
}
x=pre[top[x]]; //x passed through the thin edge and jumped onto the previous heavy chain.
}
return dep[x]<dep[y]?x:y;
}

int main() {
memset(h,-1,sizeof h);
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);
add(u,v), add(v,u);
}

dfs1(root,0);
dfs2(root,root);

while(m–) {
int a,b;
scanf("%d%d",&a,&b);
printf("%d\\n", LCA(a,b));
}

return 0;
}

/*
in:
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

out:
4
4
1
4
4
*/

【算法代码二：无注释版】

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int h[N],e[N<<1],ne[N<<1],idx;
int dep[N],pre[N],son[N],siz[N],top[N];

void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs1(int u,int fa) {
dep[u]=dep[fa]+1;
pre[u]=fa;
siz[u]=1;
for(int i=h[u]; i!=-1; i=ne[i]) {
int j=e[i];
if(j!=fa) {
pre[j]=u;
dfs1(j,u);
siz[u]+=siz[j];
if(!son[u] || siz[son[u]]<siz[j]) {
son[u]=j;
}
}
}
}

void dfs2(int x,int topx) {
top[x]=topx;
if(!son[x]) return;
dfs2(son[x],topx);

for(int i=h[x]; i!=-1; i=ne[i]) {
int j=e[i];
if(j!=pre[x] && j!=son[x]) {
dfs2(j,j);
}
}
}

int LCA(int x, int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) {
swap(x,y);
}
x=pre[top[x]];
}
return dep[x]<dep[y]?x:y;
}

int main() {
memset(h,-1,sizeof h);
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);
add(u,v), add(v,u);
}

dfs1(root,0);
dfs2(root,root);

while(m–) {
int a,b;
scanf("%d%d",&a,&b);
printf("%d\\n", LCA(a,b));
}

return 0;
}

/*
in:
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

out:
4
4
1
4
4
*/

【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/139369904 https://blog.csdn.net/hnjzsyjyj/article/details/139262893 https://blog.csdn.net/hnjzsyjyj/article/details/152203103 https://www.cnblogs.com/Atserckcn/p/18326320 https://blog.csdn.net/Lean_Feather/article/details/113057714 https://blog.csdn.net/qq_49705495/article/details/131969401 https://blog.csdn.net/hnjzsyjyj/article/details/139369904