LCA
倍增法求最近公共祖先
首先对于每个结点先进行dfs预处理它的深度，再记录下它们往父亲方向走2的0次，1次...k次步所到达的结点。在这里2的k次大于整棵树的最大深度。
预处理完后，需要查询两个点u，v的LCA时，先将u，v中深度较大的利用预处理的数组走到和另一个结点相同深度，操作次数不会超过log2|depth(u)-depth(v)|
接下来从k开始往下枚举，如果u和v往上走2的i次后不同那么它们一起往上走那么多步
预处理 O（nlogn）查询O（logn）
不仅如此我们可以动态地给树增加一些叶子结点，在预处理时还可以记录下这段路径权值最大值，最小值或权值和之类的信息。
Luogu P3379 https://www.luogu.com.cn/problem/P3379
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; struct Edge {
int t, next;
}e[<<]; //开两倍
int head[], tot; void add_edge(int x, int y) {
e[++tot].t = y;
e[tot].next = head[x];
head[x] = tot;
} int depth[], fa[][], lg[]; void dfs(int now, int fath) { //now表示当前节点，fath表示其父亲节点
fa[now][] = fath;
depth[now] = depth[fath] + ;
for (int i = ; i <= lg[depth[now]]; i++) {
fa[now][i] = fa[fa[now][i - ]][i - ]; //算法核心
}
for (int i = head[now]; i; i = e[i].next) {
if (e[i].t != fath) dfs(e[i].t, now);
}
} int LCA(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
while (depth[x] > depth[y])
x = fa[x][lg[depth[x] - depth[y]] - ]; //先跳到同一层
if (x == y) return x; //如果x==y那LCA一定就是x
for (int k = lg[depth[x]] - ; k >= ; k--) { //不断向上跳
if (fa[x][k] != fa[y][k]) { //因为要跳到LCA的下一层所以他们肯定不相等，不相等就跳过去
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][];
} int main() {
int n, m, s;
scanf("%d%d%d", &n, &m, &s);
for (int i = ; i <= n - ; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
for (int i = ; i <= n; i++) { //预先算出log2(i)+1的值，用的时候可以直接调用
lg[i] = lg[i - ] + ( << lg[i - ] == i);
}
dfs(s, );
for (int i = ; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
}
return ;
}
邻接表版本
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; const int maxn = ;
int depth[maxn], fa[maxn][];
int lg[maxn];
vector<int> e[maxn];
void add_edge(int x, int y) {
e[x].push_back(y);
}
void dfs(int u, int last) { //last是u的父亲结点
depth[u] = depth[last] + ;
fa[u][] = last;
for (int i = ; i <=lg[depth[u]]; i++) {
fa[u][i] = fa[fa[u][i - ]][i - ];
}
for (int i = ; i < e[u].size(); i++) {
if (e[u][i] != last) dfs(e[u][i], u);
}
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
while (depth[x] > depth[y]) {
x = fa[x][lg[depth[x]-depth[y]]-];
}
if (x == y) return x;
for (int k = lg[depth[x]]-; k >= ; k--) {
if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
//printf("%d\n", fa[x][0]);
}
return fa[x][];
}
int main() {
int n, m, s, x, y;
scanf("%d%d%d", &n, &m, &s);
for (int i = ; i <= n; i++) {
lg[i] = lg[i - ] + ( << lg[i - ] == i);
}
for (int i = ; i <= n - ; i++) {
scanf("%d%d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
dfs(s, );
for (int i = ; i <= m; i++) {
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return ;
}
POJ 1330 （邻接表存储）
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; int fa[][], depth[], d[];
vector<int> e[];
void dfs(int u) {
for (int i = ; i <= ; i++) {
fa[u][i] = fa[fa[u][i - ]][i - ];
}
for (int i = ; i < e[u].size(); i++) {
int v = e[u][i];
depth[v] = depth[u] + ;
fa[v][] = u;
dfs(v);
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) {
swap(u, v);
}
int t = depth[v] - depth[u];
for (int i = ; i >= ; i--) {
if ( << i & t) v = fa[v][i];
}
if (u == v) return u;
for (int i = ; i >= ; i--) {
if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
}
return fa[u][];
}
int main() {
int n, T;
scanf("%d", &T);
while (T--) {
memset(depth, , sizeof depth);
memset(fa, , sizeof fa);
memset(d, , sizeof d);
scanf("%d", &n);
int u, v;
for (int i = ; i < n; i++) {
scanf("%d%d", &u, &v);
e[u].push_back(v);
d[v]++;
}
scanf("%d%d", &u, &v);
int rt = ;
for (int i = ; i <= n; i++) if (!d[i]) rt = i;
dfs(rt);
printf("%d\n", lca(u, v));
for (int i = ; i <= n; i++) {
e[i].clear();
}
}
return ;
}
CodeForces - 697C Lorenzo Von Matterhorn
不需要求出LCA 数的移动（二叉树编号)
#include<iostream>
#include<map>
using namespace std;
typedef unsigned long long ll;
map<ll,ll> mp; int main(){
int q;
int f;
ll l,r,w;
scanf("%d",&q);
for(int i=;i<q;i++){
scanf("%d",&f);
if(f==) {
scanf("%lld%lld%lld",&l,&r,&w);
while(l!=r){
if(l>r) mp[l]+=w,l/=;
else mp[r]+=w,r/=;
}
}
else {
scanf("%lld%lld",&l,&r);
ll ans=;
while(l!=r){
if(l>r) ans+=mp[l],l/=;
else ans+=mp[r],r/=;
}
printf("%lld\n",ans);
}
}
return ;
}
倍增应用
From OI wiki
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<cmath>
const double PI = acos(-1.0);
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std; const int mod = ; int modadd(int a, int b) {
if (a + b >= mod) return a + b - mod; //加快模运算
return a + b;
} int vi[];
int go[][]; //go[i][x]表示第x个点跳2^i步后的终点
int sum[][]; //sum[i][x]表示第x个点跳2^i步之后能获得的点权和 int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = ; i <= n; i++) {
scanf("%d", &vi[i]);
}
for (int i = ; i <= n; i++) {
go[][i] = (i + k) % n + ;
sum[][i] = vi[i];
}
int logn = - __builtin_clz(n); //快捷的取2对数方法
for (int i = ; i <= logn; i++) {
for (int j = ; j <= n; j++) {
go[i][j] = go[i - ][go[i - ][j]];
sum[i][j] = modadd(sum[i - ][j], sum[i - ][sum[i - ][j]]);
}
} ll m;
scanf("%lld", &m); int ans = ;
int curx = ;
for (int i = ; m; i++) {
if (m & ( << i)) {
ans = modadd(ans, sum[i][curx]);
curx = go[i][curx];
m ^= 1ll << i; //将第i位置零 //1ll是64位的1
}
}
printf("%d", ans);
return ;
}