算法

树链剖分本身不是一种复杂的算法,其应用可以将一些数据结构(线段树,平衡树)应用到树上,对树上的路径进行查询修改。

树链就是树上的路径。树链剖分一般指将路径分为重链与轻链,这样是最优的划分。
复杂度为$log(n)$

一些概念:

  • 重儿子: 以之为根的树的结点最多的儿子
  • 轻儿子: 其它儿子
  • 重边: 根与重儿子的连边
  • 轻边: 根与轻儿子的连边
  • 重链: 重边连成的路径
  • 轻链: 轻边连成的路径

一些变量:

  • sz[u] 以u为根的树的结点数
  • deep[u] u的深度
  • fa[u] u的父亲
  • son[u] u的重儿子
  • top[u] u所在链的头
  • id[u] 剖分后结点在数据结构中的位置

划分过程:

  1. 第一遍dfs求sz[u],deep[u],fa[u],son[u]
  2. 第二遍dfs求id[u],top[u]:
    先遍历其重儿子,然后再遍历其它儿子,id[u]即为遍历顺序,轻儿子的top[u] = u。

p.s. 若栈空间不够,则改为一个bfs

对于区间[u,v]查询与更新:

  1. 若u,v在一条链上,即top[u] = top[v],直接更新,跳出
  2. 若u,v不在一条链上,即top[u] != top[v],设deep[top[u]] >= deep[top[v]],更新u到fa[top[u]],令u = fa[top[u]]

重复上述两个过程

实现

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
int sz[maxn],deep[maxn],fa[maxn],son[maxn];
int id[maxn],top[maxn],tot;

void dfs1(int u)
{
if(fa[u] != -1) deep[u] = deep[fa[u]] + 1;
sz[u] = 1;
son[u] = 0;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v != fa[u])
{
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if(sz[v] > sz[son[u]])
son[u] = v;
}
}
}

void dfs2(int u)
{
id[u] = tot++;
if(son[u])
{
top[son[u]] = top[u];
dfs2(u);
}
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v != fa[u] && v != son[u])
{
top[v] = v;
dfs2(v);
}
}
}

void init()
{
memset(fa,-1,sizeof fa);
deep[1] = top[1] = 1;
tot = 1;
dfs1(1);
dfs2(1);
}

void change(int u,int v) //query同理
{
while(top[u] != top[v])
{
if(deep[top[u]] < deep[top[v]]) swap(u,v);
update(id[top[u]],id[u]);
u = fa[top[u]];
}
if(u == v) return;
if(deep[u] > deep[v]) swap(u,v);
update(id[u],id[v]);
}

参考