源自网络

树差分 & 倍增LCA

// 链式前向星
// maxn不要随便开很大 -> 容易MLE
const int maxn = 4e4 + 5;
​
// 存无向边 -> 边要开两倍
const int maxm = (maxn - 1) << 1;
​
// 与maxn有关
// 1e6 -> 21
// 4e4 -> 17
// 1e3 -> 11
const int maxLog = 17;
​
// 起始边
int node[maxn];
​
// 辺集
struct Edge {int to, w, nxt;
}edge[maxm];
​
// 目前使用的边的条数
int edgeCnt = 0;
​
// 初始化图
void initGraph() {// 每个节点默认没有边memset(node, 0, sizeof(node));// 当前边数掷为0edgeCnt = 0;
}
​
// 加有向边(头插)
void addEdge(int from, int to, int w = -1) {edge[++edgeCnt].to = to;edge[edgeCnt].w = w;edge[edgeCnt].nxt = node[from];node[from] = edgeCnt;
}
​
// 加无向边 -> 其实就是加两条方向相反的有向边
void addUndirectedEdge(int from, int to, int w = -1) {addEdge(from, to, w);addEdge(to, from, w);
}
​
// 维护深度信息
int deep[maxn];
​
// 维护多级祖先节点 -> 方便快速跳跃
int fa[maxn][maxLog + 1]; 
​
// 树差分思想 -> 当前节点到根节点的距离
int dis[maxn];
​
// 初始化
void init() {// 初始化链式前向星initGraph();// 深度默认为0memset(deep, 0, sizeof(deep));// 到根节点距离默认掷为0memset(dis, 0, sizeof(dis));// 祖先数组都设为-1 -> 没有祖先 // 这里使用-1是因为节点下标可能从0起// 使用-1时需谨慎 -> 很容易数组越界memset(fa, 0xff, sizeof(fa));
}
​
/** 深度优先搜索
*   @Param root:   当前节点
*   @Param father: 当前节点的直接祖先
*   @Param w:      当前节点入边的权重
*/
void dfs(int root, int w = 0, int father = -1) {// 父节点不为-1时才处理 -> 防下标越界if (~father) {// 当前节点的直接祖先设为 @fatherfa[root][0] = father;// 维护当前节点的深度信息 -> 为父节点深度 + 1 deep[root] = deep[father] + 1;// 维护当前节点到根节点的距离 -> 父节点距离 + 入边边权dis[root] = dis[father] + w;}// 2^i祖先为2^i-1级祖先的2^i-1级祖先 -> 详细讲解见视频for (int i = 1; (1 << i) <= deep[root]; i++)fa[root][i] = fa[fa[root][i - 1]][i - 1];// 深度搜索所有子节点for (int i = node[root]; i; i = edge[i].nxt) {// 存无向边 -> 会遍历回父节点 -> 防重复遍历if (edge[i].to == father) continue;// 搜索子节点dfs(edge[i].to, edge[i].w, root);}
}
​
// LCA核心
int lca(int nodeA, int nodeB) {// 减少代码量 -> 默认nodeB深度更大 -> 若nodeA深度更大 -> AB互换身份 -> 不影响结果if (deep[nodeA] > deep[nodeB]) swap(nodeA, nodeB);// nodeB 上跳至与 nodeA 深度相同// 从大步长开始跳跃for (int i = maxLog; i >= 0; i--) {// 注意判断 **father = -1** 的情况if ((fa[nodeB][i] != -1) && deep[fa[nodeB][i]] >= deep[nodeA]) nodeB = fa[nodeB][i];// nodeA 是 nodeB 祖先 -> 直接返回 nodeA -> 视频开头有讲解if (nodeA == nodeB) return nodeA;}for (int i = maxLog; i >= 0; i--) {// 不是节点跳到一起，而是祖先跳到一起 -> 因为两节点 2^20 级祖先肯定相等，没得判断了// 同样注意判断 father = -1 的情况if ((fa[nodeA][i] != -1) && (fa[nodeB][i] != -1) && fa[nodeA][i] != fa[nodeB][i]) {nodeA = fa[nodeA][i];nodeB = fa[nodeB][i];}}// 达到临界状态 -> 返回任意节点的直接祖先return fa[nodeA][0];
}

Tarjan

const int N = 5e5 + 7;
​
int n, m, u, v, s;
int tot = 0, st[N], to[N << 1], nx[N << 1], fa[N], ans[N], vis[N];
struct note { int node, id; }; //询问以结构体形式保存
vector<note> ques[N];
​
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
​
//并查集的getfa操作，路径压缩
inline int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); } 
​
void dfs(int u, int from) {//将u的儿子合并到ufor (int i = st[u]; i; i = nx[i]) if (to[i] != from) dfs(to[i], u), fa[to[i]] = u; //处理与u有关的询问int len = ques[u].size(); //对应的v已经访问并回溯时，LCA(u,v)就是v的fa里深度最小的一个也就是getfa(v)for (int i = 0; i < len; i++) if (vis[ques[u][i].node]) ans[ques[u][i].id] = getfa(ques[u][i].node); //访问完毕回溯vis[u] = 1; 
}

朴素算法

// 和倍增LCA几乎一样
const int maxn = 1e6 + 5;
const int maxm = maxn - 1;
int node[maxn];
​
struct Edge {int to, w, nxt;
}edge[maxm];
int edgeCnt = 0;
​
void initGraph() {memset(node, 0, sizeof(node));edgeCnt = 0;
}
​
void addEdge(int from, int to, int w = -1) {edge[++edgeCnt].to = to;edge[edgeCnt].w = w;edge[edgeCnt].nxt = node[from];node[from] = edgeCnt;
}
​
void addUndirectedEdge(int from, int to, int w = -1) {addEdge(from, to, w);addEdge(to, from, w);
}
​
int deep[maxn];
int fa[maxn];
​
void init() {initGraph();memset(deep, 0, sizeof(deep));memset(fa, 0xff, sizeof(fa));
}
​
int lca(int nodeA, int nodeB) {if (deep[nodeA] > deep[nodeB]) swap(nodeA, nodeB);while (deep[nodeB] != deep[nodeA]) nodeB = fa[nodeB];while (nodeA != nodeB) {nodeA = fa[nodeA];nodeB = fa[nodeB];}return nodeA;
}
​
void dfs(int root, int father = -1) {deep[root] = deep[father] + 1;fa[root] = father;for (int i = node[root]; i; i = edge[i].nxt) {if (edge[i].to == father) continue;dfs(edge[i].to, root);}
}