前言：

本系列是學習了董曉老師所講的知識點做的筆記

董曉算法的個人空間-董曉算法個人主頁-嗶哩嗶哩視頻 (bilibili.com)

?動態規劃系列（還沒學完）

【董曉算法】動態規劃之線性DP問題-CSDN博客

【董曉算法】動態規劃之背包DP問題（2024.5.11）-CSDN博客

【董曉算法】動態規劃之背包DP與樹形DP-CSDN博客

字符串系列（）

【董曉算法】競賽常用知識之字符串1-CSDN博客

【董曉算法】競賽常用知識之字符串2-CSDN博客

數據結構系列（未學完）

【董曉算法】競賽常用知識點之數據結構1-CSDN博客

搜索系列

[董曉算法]搜索相關題目及模板-CSDN博客

圖論系列?

【董曉算法】算法知識之圖論1（拓撲排序，多種最短路算法）-CSDN博客

【董曉算法】競賽常用知識之圖論2（最小環，最小生成樹）-CSDN博客

最近公共祖先

倍增算法

倍增算法是最經典的求 LCA 算法
dep]存u點的深度。fa[u][i] 存從 u 點向上跳 2 層的祖先結點。

步驟：

1.dfs 一遍，創建 ST 表（倍增遞推，fa[u][i]=fa[fa[u][i-1]][i-1])

2.利用 ST 表求 LCA

const int N=5e5+10;
int n,m,s;
vector<int> e[N];
int dep[N],fa[N][22];void dfs(int u,int father){ //樹增dep,fadep[u]=dep[father]+1; fa[u][0]=father;for(int i=1; i<=20; i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v : e[u])if(v!=father) dfs(v,u);
}
int lca(int u,int v){ //樹增lcaif(dep[u]<dep[v]) swap(u,v);//先跳到同一層for(int i=20; i>=0; i--)if(dep[fa[u][i]]>=dep[y]) u=fa[u][i];if(u==v) return v;for(int i=20; i>=0; i--)if(fa[u][i]!=fa[v][i]) x=fa[u][i],y=fa[v][i];return fa[u][0];
}

Tarjan 算法

Tarjan(塔揚)算法是一種離線算法，巧妙利用并查集維護祖先結點

1.從根開始深搜遍歷，入u時 打標記

2.枚舉u的兒子v、遍歷完v的子樹，回u時 把v指向 u。

3.遍歷完u的兒子們，離u時 枚舉以 u為起點的查詢，若終點 v被搜過則查找 v的根，即 uv 的 LCA，答案記入 ans0。

4.遞歸遍歷完整顆樹，得到全部查詢答案。

?i是第i個查詢?

vector<int> e[N];
vector<pair<int,int>>query[N];
int fa[N],vis[N],ans[M]; 
int find(int u){if(u==fa[u]) return u;return fa[u]=find(fa[u]);
}
void tarjan(int u){vis[u]=true;//標記u已訪問for(auto y : e[u]){if(!vis[y]){tarjan(y);fa[y]=u;//回到u時v指向u    }        }//離開u時找LCAfor(auto q : query[u]){int y=q.first,i=q.second;if(vis[y])ans[i]=find(y);}
}

樹鏈剖分

概念

1. 重兒子：父結點的所有兒子中子樹結點數目最多的結點
2. 輕兒子：父結點中除重兒子以外的兒子
3. 重邊:父結點和重兒子連成的邊
4. 輕邊:父結點和輕兒子連成的邊
5. 重鏈：由多條重邊連接而成的路徑

1.整棵樹會被剖分成若干條重鏈。

2.輕兒子一定是每條重鏈的頂點。

3.任意一條路徑被切分成不超過 logn 條鏈

流程

1.第一遍 dfs，搞出 fa.dep.son 數組
2.第二遍 dfs，搞出 top 數組
3.讓兩個游標沿著各自的重鏈向上跳，跳到同一條重鏈上時，深度較小的那個游標所指向的點，就是 LCA

vector<int> e[N];
int fa[N],son[N],dep[N],siz[N];
int top[N];
void dfs1(int u,int father){ //搞fa,dep,son son存u的重兒子fa[u]=father;dep[u]=dep[father]+1;siz[u]=1;for(int v:e[u]){if(v==father) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}
}
void dfs2(int u,int t){ //搞toptop[u]=t;  //記錄鏈頭if(!son[u]) return; //無重兒子dfs2(son[u],t);     //搜重兒子for(int v:e[u]){if(v==fa[u]||v==son[u])continue;dfs2(v,v); //搜輕兒子}
}
int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}return dep[u]<dep[v]?u:v;
}