LCA 学习笔记

模板及讲解
倍增思想,维护$deep[i], pre[i][j]$为点$i$的深度和点$i$的$2^j$个祖先结点
然后对于每一对$x, y$求$LCA(x, y)$,先把深的结点提上来和浅结点深度相同,如果此时$x, y$都相同,说明$x, y$在同侧,输出$x, y$任意一个即可,否则再一起提上来直到两点相等,输出$pre[x][0]$或者$pre[y][0]$

跳的时候跳二进制,即
设$del = deep[b] - deep[a] (deep[b] >= deep[a])$
如果 $del = 5$, 二进制为$101$
那么从左往右扫描,第$i$位为$1$的就跳$2^i$个点
$del = 5$时,跳$2^2$和$2^0$即可

常见题型
1、LCA思想
Q:一棵树,询问一个路径u->v,先再路径上选取一个a1, 再在后面选取一个a2, 使得(a1-a2)最大
解:运用LCA(倍增)思想。
例题:poj 3728
2、结合dfs序
Q:一棵树,有两种操作:1、求u, v路径上的权值和 2、修改一条边的权值
解:修改边权会使far数组改变,那么用数据结构维护far数组
例题:poj2763

相关代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);
const int MAXN = 40000 + 5, logs = 21;
struct edge
{
int x, y, c;
}ed[2*MAXN];
int en;
int n, m;
vector<int> G[MAXN];
int deep[MAXN], far[MAXN], pre[MAXN][logs+1];
//深度,距离根节点距离(权值和),结点的2^i祖先
void dfs(int x, int p)//搜索一次初始化记录
{
pre[x][0] = p;
for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1];//运用性质求2^i祖先
for (int i=0;i<G[x].size();i++)//向下搜索
{
int v = ed[G[x][i]].y;
if (v!=p)
{
deep[v] = deep[x] + 1;
far[v] = far[x] + ed[G[x][i]].c;
dfs(v,x);
}
}
}
int lca(int a, int b)
{
if (deep[a]>deep[b]) swap(a, b);
for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i];//抬升到同一高度
//也可以 dep = deep[b] - deep[a]; if ((dep>>1)&1)
if (a==b) return a;//如果在同侧
for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];//继续不断往上提
return pre[a][0];//最终答案是a或者b的父亲结点
}
void addedge(int x, int y, int c)
{
en++; ed[en].x = x; ed[en].y = y; ed[en].c = c; G[x].push_back(en);
en++; ed[en].x = y; ed[en].y = x; ed[en].c = c; G[y].push_back(en);
}
void init()
{
for (int i=1;i<=n;i++) G[i].clear();
en = 0;
scanf("%d%d", &n, &m);
for (int i=1;i<n;i++)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
addedge(x, y, c);
}
}
void solve()
{
ms(pre, 0); ms(deep, 0); ms(far, 0); dfs(1, 0);
for (int i=1;i<=m;i++)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", far[x]+far[y]-2*far[lca(x,y)]);
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
init();
solve();
}
return 0;
}

------ 本文结束 ------