树基础

无根树

图论中的树和现实生活中的树长得一样，只不过我们习惯于处理问题的时候把树根放到上方来考虑。这种数据结构看起来像是一个倒挂的树，因此得名

一个没有固定根结点的树称为 无根树。无根树有几种等价的形式化定义：

  • 有 n 个结点，n-1 条边的连通无向图
  • 无向无环的连通图
  • 任意两个结点之间有且仅有一条简单路径的无向图
  • 任何边均为桥的连通图
  • 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

连通分量中经常出现割点和桥的定义

在无根树的基础上，指定一个结点称为 根 ，则形成一棵 有根树

注意：一般有根树在很多时候仍以无向图表示，只规定了结点之间的上下级关系，无根树就是节点之间正反关系都存

树的定义

适用于无根树和有根树

  • 森林：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林
  • 生成树 ：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 n-1 条，将所有顶点连通
  • 结点的深度 ：到根结点的路径上的边数
  • 树的高度 ：所有结点的深度的最大值
  • 无根树的叶结点 ：度数不超过 1 的结点

因为无根树根没有确定，所以度数不超过 1 的结点都有可能是叶节点

  • 有根树的叶结点 ：没有子结点的结点

只适用于有根树

  • 父亲：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。 根结点没有父结点
  • 祖先 ：一个结点到根结点的路径上，除了它本身外的结点。 根结点的祖先集合为空
  • 子结点 ：如果 u 是 v 的父亲，那么 v 是 u 的子结点。子结点的顺序一般不加以区分，二叉树是一个例外
  • 兄弟 ：同一个父亲的多个子结点互为兄弟
  • 后代 ：子结点和子结点的后代
    或者理解成：如果 u 是 v 的祖先，那么 v 是 u 的后代
  • 子树 ：删掉与父亲相连的边后，该结点所在的子图

特殊的树

  • 链 ：满足与任一结点相连的边不超过 1 条的树称为链

  • 菊花/星星 ：满足存在 u 使得所有除 u 以外结点均与u相连的树称为菊花

  • 有根二叉树：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点，大多数情况下， 二叉树 一词均指有根二叉树

  • 完整二叉树 ：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点要么是树叶，要么左右子树均非空
  • 完全二叉树 ：只有最下面两层结点的度数可以小于 2 ，且最下面一层的结点都集中在该层最左边的连续位置上
  • 完美二叉树 ：所有叶结点的深度均相同的二叉树称为完美二叉树，又称满二叉树

存储方法

只记录父节点

只用一个 fa[] 来记录每个节点的父亲节点——获取信息较少不便于进行自顶向下的遍历，常用于自底向上的递推问题

邻接表

  • 对于无根树就给每一个节点开一个 vector 记录与其相连的所有点
1
vector<int> vec[N];
  • 对于有根树为了确保上下关系所以每个节点的 vector 只记录与其相连的子节点，为了方便遍历还可以另开一个数组用来给每个节点记录其父节点
1
2
vector<int> child[N];
int fa[N];

左孩子右兄弟表示法

对于有根树，存在一种简单的表示方法。首先，给每个结点的所有子结点任意确定一个顺序。后为每个结点记录两个值：其 第一个子结点 child[u] 和其 下一个兄弟结点 sib[u] 。若没有子结点，则 child[u] 为空；若该结点是其父结点的最后一个子结点，则 sib[u] 为空。

遍历一个结点的所有子结点可由如下方式实现：

1
2
3
4
5
6
7
int v = child[u];// 从第一个子结点开始
while (v != EMPTY_NODE){
  // ...
  // 处理子结点 v
  // ...
  v = sib[v];// 转至下一个子结点，即 v 的一个兄弟
}

树上DFS

以有根二叉树为例

先序遍历

1
2
3
4
5
6
7
/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T){
    if(T==NULL)return;
    printf("%c", T->data);/*显示结点数据，可以更改为其他对结点操作*/
    PreOrderTraverse(T->lchild);/*再先序遍历左子树*/
    PreOrderTraverse(T->rchild);/*最后先序遍历右子树*/
}

中序遍历

1
2
3
4
5
6
7
/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T){
    if(T==NULL)return;
    InOrderTraverse(T->lchild);/*中序遍历左子树*/
    printf("%c", T->data);/*显示结点数据，可以更改为其他对结点操作*/
    InOrderTraverse(T->rchild);/*最后中序遍历右子树*/
}

后序遍历

1
2
3
4
5
6
7
/*二叉树的后序遍历递归算法*/
void InOrderTraverse(BiTree T){
    if(T==NULL)return;
    InOrderTraverse(T->lchild);/*后序遍历左子树*/
    InOrderTraverse(T->rchild);/*后序遍历右子树*/
    printf("%c", T->data);/*最后显示结点数据，可以更改为其他对结点操作*/
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*二叉树的层序遍历算法*/
void LevelOrder(TreeNode *root){
    std::queue<TreeNode *> q;
    TreeNode *front;

    if (root==NULL)return;
	q.push(root);
    
    while(!q.empty()){
        front=q.front();
        q.pop();

    	if(front->left)/*左子树非空加入队列*/
        q.push(front->left);

        if(front->right)/*右子树非空加入队列*/
        q.push(front->right);
		
		printf("%c ",front->data);/*输出当前节点*/
    }
}

树上BFS

无根树

树的遍历一般为深度优先遍历，这个过程中最需要注意的是避免重复访问结点

由于树是无环图，因此只需记录当前结点是由哪个结点访问而来，此后进入除该结点外的所有相邻结点，即可避免重复访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int u,int from){//当前节点和其父节点
  // 递归进入除了from之外的所有子结点
  // 对于出发结点,from 为空,故会访问所有相邻结点，这与期望一致
  for(int v:vec[u])
    if(v!=from){
      dfs(v, u);
    }
}

signed main()
{
	//一般数的节点从1开始遍历
	int EMPTY_NODE=0;//设一个不存在的编号
	int root=1;//任取一个结点作为出发点
	dfs(root,EMPTY_NODE);
}

有根树

因为每个节点的vector存的就是子节点不存在重复访问的问题所以直接遍历节点的vector就可以了

DFS序

1
2
3
4
5
6
7
8
int dfs_order[maxn],tot=0;//存储顺序输出的节点数组和寄存指针
vector<int> G[maxn];

void dfs(int x){
	dfs_order[tot++]=x;//将遍历的点存起来
	for(auto u:G[x])
	dfs(i); 
}

这个代码只是给出一种DFS序遍历树的形式，做题要具体问题具体分析需要在看懂了这几行代码的基础上自己写DFS

  • DFS是深度优先的，所以对于一个点，它会先遍历完它的所有子节点（也就是一路摸到黑，不撞墙不回头），再去遍历他的兄弟节点以及其他节点

  • 对于一棵树的DFS序来说，这个点和他所有的子节点会被存储在连续的区间之中

欧拉序

从根节点出发，按照DFS顺序并绕回根节点的顺序（即回溯再次经过的点也要记录）输出节点：1 2 4 7 7 8 8 4 2 3 5 9 9 5 6 6 3 1

欧拉序的主要作用体现下文在树链剖分中

最近公共祖先（ LCA ）

最近公共祖先简称 LCA 。两个节点的最近公共祖先就是这两个点的公共祖先里面离根最远的那个。 为了方便，我们记某 S=v1,v2,…,vn 点集的最近公共祖先为 LCA(v1,v2,…,vn) 或 LCA(S)

性质

  • LCA(u)=u
  • u 是 v 的祖先，当且仅当 LCA(u,v)=u
  • 如果 u 不为 v 的祖先并且 v 不为u的祖先，那么 u ，v 分别处于 LCA(u,v) 的两颗不同子树中
  • 前序遍历中，LCA(S) 出现在所有 S 中元素之前，后序遍历中 LCA(S) 则出现在所有S中元素之后
  • 两点集并的最近公共祖先的最近公共祖先：LCA(AUB)=LCA(LCA(A),LCA(B))
  • 两点的最近公共祖先必定处在树上两点间的最短路上
  • length(u,v)=dis(u)+dis(v)-2*dis(LCA(u,v)) ，其中 length 是树上两点间的距离，dis代表某点到树根的距离

朴素算法

可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 LCA 。 或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。

复杂度分析

朴素算法预处理时需要 DFS 整棵树，时间复杂度为 O(n) ，单次查询时间复杂度为 O(n) 。但由于随机树高为 O(logn) ，所以朴素算法在随机树上的单次查询时间复杂度为 O(logn)

倍增算法

倍增算法是最经典的 LCA 求法，他是朴素算法的改进算法

通过预处理pre[x][i]数组，游标可以快速移动，大幅减少了游标跳转次数。pre[x][i] 表示点 x 的第 2i个祖先。 pre[x][i] 数组可以通过 DFS 预处理出来

现在我们看看如何优化这些跳转：在调整游标的第一阶段中，我们可以计算出 u ，v 两点的深度之差，设其为y。通过将y进行二进制拆分，我们将 y 次游标跳转优化为 count_one_in_binary_representation(y) 次游标跳转。 在第二阶段中，我们从最大的 i 开始循环尝试，一直尝试到 0（包括 0 ），如果 pre[u][i]!=pre[v][i] ，则令 u=pre[u][i];v=pre[v][i] ，那么最后的 LCA 为 pre[u][0]

复杂度分析

倍增算法的预处理时间复杂度为 O(nlogn)，单次查询时间复杂度为 O(logn) 。 另外倍增算法可以通过交换 pre 数组的两维使较小维放在前面。这样可以减少 cache miss 次数，提高程序效率

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e4+5;//最大顶点数

struct Edge{
    int to,next,val;
}e[maxn<<1];//链式前向星存边,多开一倍空间存反向边

int head[maxn],tot;

int t,n,m;//样例数、顶点数和查询数
int dep[maxn],pre[maxn][21];
//记录当前节点到根节点的距离，自己深度和第2^i个祖先

void init(){
    tot=0;
    memset(head,-1,sizeof head);
}

void add(int x,int y,int val){
    e[tot].to=y,e[tot].val=val,e[tot].next=head[x],head[x]=tot++;
}

void dfs(int x,int from){//预处理祖先数组
    dep[x]=dep[from]+1;
    pre[x][0]=from;
    for(int i=1;(1<<i)<=dep[x];i++){
        pre[x][i]=pre[pre[x][i-1]][i-1];
    }

    for(int i=head[x];~i;i=e[i].next){
        int y=e[i].to;
        if(y!=from) {
            dfs(y,x);
        }
    }
}

int lca(int x,int y){//先单个跳到一样深度在一起跳
    if(dep[x]<dep[y])swap(x, y);
    for(int i=19;i>= 0;i--) {
        if(dep[x]-(1<<i)>=dep[y]){
            x=pre[x][i];
        }
    }
    if(x==y)return x;//说明y是x的祖先

    for(int i=19;i>=0;i--){//尽量往高跳
        if (pre[x][i]!=pre[y][i]){
            x=pre[x][i],y=pre[y][i];
        }
    }
    return pre[x][0];//LCA(x,y)
}

signed main(){
    int t;cin>>t;
    while(t--){
        init();
        cin>>n>>m;
        for(int i=1;i<n;i++){
            int x,y,val;
            cin>>x>>y>>val;
            add(x,y,val),add(y,x,val);
        }
        dfs(1,0);
        int x,y,node;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            node=lca(x,y);
            cout<<node<<endl;//输出LCA
        }
    }
    return 0;
}

Tarjan算法

参考博客 详细讲解演示看这篇转载的博客讲的炒鸡好

Tarjan算法是一种离线算法 ，需要使用并查集记录某个结点的祖先结点。做法如下：

  • 首先接受输入（链式前向星）、查询（存储另一个数组）即离线操作
  • 然后对其进行一次 DFS 遍历，同时使用 vis 数组进行记录某个结点是否被访问过、fa 记录当前结点的父亲结点
  • 其中涉及到了回溯思想，我们每次遍历到某个结点的时候，认为这个结点的根结点就是它本身。让以这个结点为根节点的 DFS 全部遍历完毕了以后，再将这个结点的根节点设置为这个结点的父一级结点
  • 回溯的时候，如果以该节点为起点 查询边的另一个结点也恰好访问过了，则直接更新查询边的 LCA 结果
  • 将存储的答案输出

注意：因为在 Tarjan 过程中尝试寻找查询边的 LCA ，所以必须先存储下来查询了哪些边，最后经得到的 LCA 顺序存储在 ans 数组中输出就是答案顺序（离线操作）

复杂度分析

Tarjan算法需要初始化并查集，所以预处理的时间复杂度为 O(n) ，Tarjan 算法处理所有询问的时间复杂度为O(n+m)。但是 Tarjan 算法的常数比倍增算法大。Tarjan 算法中使用的并查集性质比较特殊，在仅使用路径压缩优化的情况下，单次调用 find() 函数的时间复杂度为均摊 O(1)，而不是 O(logn)

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
83
//LCA:离线操作+Tarjan
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;//最大顶点数

inline int read(){//快读
    int x=0,f=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^'0');
    return f?-x:x;
}

int n,m,u,v,val,s;//顶点数,查询数,存储两个节点及边长,根节点
int tot=0;//寄存指针
int head[N],to[N<<1],nex[N<<1],fa[N],ans[205],vis[N];
//链式前向星多开一倍空间存反向边,ans顺序记录答案

struct note{//询问以结构体形式保存
    int node,id;//查询边的一个顶点和查询边的次序
};

vector<note> ques[N];//存储顶点需要查询的边的另一端点

inline void add(int u,int v,int val){
    to[++tot]=v,nex[tot]=head[u],head[u]=tot;
}

inline int getfa(int x){//并查集的getfa操作，路径压缩
    return fa[x]==x?x:fa[x]=getfa(fa[x]); 
}

void init(){//初始化并查集和链式前向星
    for(int i=1;i<=n;i++){
        fa[i]=i;
        ques[i].clear();//问题边清空
    }

    tot=0;
    memset(head,-1,sizeof head);
}

void tarjan(int u,int from){//tarjan寻找LCA
    for(int i=head[u];i;i=nex[i]) 
    if(to[i]!=from)//不往回走就向下遍历
    tarjan(to[i],u),fa[to[i]]=u;//将u的儿子合并到u

    //处理与u有关的询问
    int len=ques[u].size();
    for(int i=0;i<len;i++) 
    if(vis[ques[u][i].node]){//对应的v已经访问并回溯时，LCA(u,v)就是v的fa里深度最小的一个也就是getfa(v)
        ans[ques[u][i].id]=getfa(ques[u][i].node);//记录LCA
    }

    //访问完毕回溯
    vis[u]=1;
}

void solve(){
    n=read(),m=read();//顶点数、查询边数和根节点序号
    init();//存完顶点数初始化
    for(int i=1;i<n;i++){//存储n-1条边
        u=read(),v=read(),val=read();
        add(u,v,val),add(v,u,val);
    }
    for(int i=1;i<=m;i++){
        u=read(),v=read();
        ques[u].push_back((note){v,i}),ques[v].push_back((note){u,i});//记下询问编号便于输出
    }
    s=1;//规定根节点为1开始找
    tarjan(s,0);
    for(int i=1;i<=m;i++)
    printf("%d\n",ans[i]);//输出答案
}

signed main()
{
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

其实为什么要将查询的连个顶点正反两次存储：因为在上面过程我们不能保证遍历 u 时 v 已经回溯那么这时就不能进行查找 LCA ，存正反两次正好完美解决了上述情况，经过了这次 u 被回溯后遍历到 v 一定能查找LCA

利用欧拉序转换为RMQ问题

将树看成一个无向图，u 和 v 的公共祖先一定在 u 与 v 之间的最短路径上：

  • DFS : 从树T的根开始, 进行深度优先遍历（将树T看成一个无向图）, 并记录下每次到达的顶点, 以及这个点的深度, 第一个的结点是 root(T) , 每经过一条边都记录它的端点。由于每条边恰好经过2次，因此一共记录了2n-1个结点，用dfn[1,…,2n-1]来表示

  • 计算 first : 用 first[i] 表示 dfn 数组中第一个值为 i 的元素下标，即如果 first[u]<first[v] 时， DFS 访问的顺序是 。虽然其中包含 u 的后代，但深度最小的还是 u 与 v的公共祖先

  • 计算 ST 表：用 f[2*N]][M] 记录以 dfn[] 中 i 位置对应的节点为第一个节点，和长度2j为的区间另一端点对应的节点的最近公共祖先在 dfn[] 中的位置

  • RMQ 查询：在线查询两个端点的最近公共祖先—— first(LCA(u,v))=min{first[k]|k属于first[u]...first[v]}

不难理解：从 u 走到 v 的过程中一定会经过 LCA(u,v) ，但不会经过 LCA(u,v) 的祖先。因此，从u走到 v 的过程中经过的欧拉序最小的结点就是 LCA(u,v)

注意：先预处理所有的可能，然后在线每次以复杂度为 O(1) 查询两点的最近 LCA ，所以是在线操作，无法中途修改图的关系

复杂度分析

用 DFS 计算欧拉序列的时间复杂度是 O(n) ，且欧拉序列的长度也是 O(n) ，所以 LCA 问题可以在 O(n) 的时间内转换为等规模的 RMQ 问题，使用 ST 表解决 RMQ 问题不支持在线修改，需处理的时间是 O(nlogn)

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
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//最大单元数
const int M=20;//2^i中i的最大值也就是某段区间的最大长度

int n,m;
int pcnt=0,tot=0;//存储DFS序数组的寄存指针和链式前向星的寄存指针
int first[N];//记录第一个序号为i的节点下标
int dfn[2*N];//每个位置记录访问节点的DFS序
int depth[2*N];//记录DFS序中各个位置对应节点的深度
int f[2*N][M];//记录以dfn[]中i位置对应的节点为第一个节点，和长度2^j为的区间另一端点对应的节点的最近公共祖先在dfn[]中的位置

int head[N];//记录
struct node{
    int nxt,v;//当前点所处边的下一条边的数组下标和另一个顶点
}edge[2*N];

void init(){
    pcnt=0;
    tot=0;
    memset(head,-1,sizeof head);
}

void add(int x,int y){
    tot++;
    edge[tot].nxt=head[x];
    head[x]=tot;
    edge[tot].v=y;
}

void dfs(int u,int from,int dep){//当前节点,父节点,深度
    dfn[++pcnt]=u;
    first[u]=pcnt;
    depth[pcnt]=dep;
    for(int i=head[u];i+1;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==from) continue;
        dfs(v,u,dep+1);
        dfn[++pcnt]=u;
        depth[pcnt]=dep;
    }
}

void ST(){
    for(int i=1;i<=pcnt;i++)
        f[i][0]=i;

    for(int j=1;j<M;j++)
        for(int i=1;i+(1<<j)-1<=pcnt;i++){
            int a=f[i][j-1],b=f[i+(1<<(j-1))][j-1];
            if(depth[a]<depth[b])f[i][j]=a;//两个位置对应节点的深度较小的就是LCA
            else f[i][j]=b;
        }
}

int RMQ(int l,int r){
    int k=log((double)(r-l+1))/log(2.0);
    int a=f[l][k],b=f[r-(1<<k)+1][k];
    if(depth[a]<depth[b])return a;
    else return b;
}

int LCA(int L,int R){
    int l=first[L];
    int r=first[R];
    if(l>r)swap(l, r);//回溯的点为查询区间左端
    int pos=RMQ(l, r);
    return dfn[pos];//获取的是位置，输出的是对应节点
}

signed main(){
    while(cin>>n>>m){
        init();
        for(int i=1;i<=n-1;i++){
            int x,y;cin>>x>>y;
            add(x,y),add(y,x);
        }
        dfs(1,0,1);
        ST();
        for(int i=1;i<=m;i++){
            int a,b;cin>>a>>b;
            cout<<LCA(a,b)<<endl;
        }
    }
    return 0;
}

树链剖分解决

有点杀鸡用牛刀的感觉了，下面树链剖分有讲，基本不用

模板

模板题：n 个点 m 次询问无根树中两点的最短路径（其实就是找 LCA 并且维护距离）

倍增算法

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
//节点序号从1开始
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e4+5;

struct Edge{
    int to,nex,val;
}e[maxn<<1];//链式前向星存边

int head[maxn],tot;

int t,n,m;//样例数、顶点数和查询数
int dis[maxn],dep[maxn],pre[maxn][21];
//记录当前节点到根节点的距离，自己深度和第2^i个祖先

void init(){
    memset(head,-1,sizeof head);
    memset(dis,0x3f,sizeof dis);//其实不初始化也行
    dis[1]=dis[0]=0;//注意特殊距离
    tot=0;
}

void add(int x,int y,int val){
    e[tot].to=y,e[tot].val=val,e[tot].nex=head[x],head[x]=tot++;
}

void dfs(int x,int from){//预处理祖先数组
    dep[x]=dep[from]+1;
    pre[x][0]=from;
    for(int i=1;(1<<i)<=dep[x];i++){
        pre[x][i]=pre[pre[x][i-1]][i-1];
    }

    for(int i=head[x];~i;i=e[i].nex){
        int y=e[i].to;
        if(y!=from) {
            dis[y]=dis[x]+e[i].val;
            dfs(y,x);
        }
    }
}

int lca(int x,int y){//先单个跳到一样深度在一起跳
    if(dep[x]<dep[y])swap(x, y);
    for(int i=19;i>= 0;i--) {
        if(dep[x]-(1<<i)>=dep[y]){
            x=pre[x][i];
        }
    }
    if(x==y)return x;//说明y是x的祖先

    for(int i=19;i>=0;i--){//尽量往高跳
        if (pre[x][i]!=pre[y][i]){
            x=pre[x][i],y=pre[y][i];
        }
    }
    return pre[x][0];//LCA(x,y)
}

signed main(){
    int t;cin>>t;
    while(t--){
        init();
        cin>>n>>m;
        for(int i=1;i<n;i++){
            int x,y,val;
            cin>>x>>y>>val;
            add(x,y,val),add(y,x,val);
        }
        dfs(1,0);
        int x,y,node;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            node=lca(x,y);
            cout<<dis[x]+dis[y]-2*dis[node]<<endl;
        }
    }
    return 0;
}

Tarjan算法

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
83
84
85
86
//Tarjan离线操作:节点序号从1开始
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;//最大顶点数

inline int read(){//快读
    int x=0,f=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^'0');
    return f?-x:x;
}

int n,m,u,v,val,s;//顶点数,查询数,存储两个节点及边长,根节点
int tot=0;//寄存指针
int st[N],to[N<<1],nex[N<<1],graph[N<<1],fa[N],ans[205],vis[N],dis[N];
//链式前向星多开一倍空间存反向边,ans顺序记录答案

struct note{//询问以结构体形式保存
    int node,id;//查询边的一个顶点和查询边的次序
};

vector<note> ques[N];//存储顶点需要查询的边的另一端点

inline void add(int u,int v,int val){
    to[++tot]=v,nex[tot]=st[u],graph[tot]=val,st[u]=tot;
}

inline int getfa(int x){//并查集的getfa操作，路径压缩
    return fa[x]==x?x:fa[x]=getfa(fa[x]); 
}

void init(){//初始化并查集和链式前向星
    for(int i=1;i<=n;i++){
        fa[i]=i;
        ques[i].clear();//问题边清空
    }

    tot=0;
    memset(st,-1,sizeof st);
    memset(dis,0x3f,sizeof dis);//其实不初始化也行
    dis[1]=dis[0]=0;//注意特殊距离
}

void tarjan(int u,int from){//tarjan寻找LCA
    for(int i=st[u];i;i=nex[i]) 
    if(to[i]!=from)//不往回走就向下遍历
    dis[to[i]]=dis[u]+graph[i],tarjan(to[i],u),fa[to[i]]=u;//将u的儿子合并到u

    //处理与u有关的询问
    int len=ques[u].size();
    for(int i=0;i<len;i++) 
    if(vis[ques[u][i].node]){//对应的v已经访问并回溯时，LCA(u,v)就是v的fa里深度最小的一个也就是getfa(v)
        int tot=getfa(ques[u][i].node);//记录LCA
        ans[ques[u][i].id]=dis[u]+dis[ques[u][i].node]-2*dis[tot];//存入答案
    }
    
    //访问完毕回溯
    vis[u]=1;
}

void solve(){
    n=read(),m=read();//顶点数、查询边数和根节点序号
    init();//存完顶点数初始化
    for(int i=1;i<n;i++){//存储n-1条边
        u=read(),v=read(),val=read();
        add(u,v,val),add(v,u,val);
    }
    for(int i=1;i<=m;i++){
        u=read(),v=read();
        ques[u].push_back((note){v,i}),ques[v].push_back((note){u,i});//记下询问编号便于输出
    }
    s=1;//规定根节点为1开始找
    tarjan(s,0);
    for(int i=1;i<=m;i++)
    printf("%d\n",ans[i]);//输出答案
}

signed main()
{
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

树的重心与直径

树的重心

参考博客

定义：树上一节点最大子树的节点数最小

性质：

  • 删除重心后所得的所有子树，节点数不超过原树的 1/2 ，一棵树最多有两个重心
  • 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等
  • 两个树通过一条边合并，新的重心在原树两个重心的路径上
  • 树删除或添加一个叶子节点，重心最多只移动一条边

定义求解

先选择一个节点作为根节点然后 dfs 其所有子树并记录最大子树中的节点数，因为根节点的子树又可以作为其子树的根节点所以可以递归求解。每 dfs 一次就得到了当前节点的最大子树中的节点数所以尝试更新答案

无权节点常用模板

一般也就用这个模板，涉及点权的树的重心比较难

模板题：有 T 组数据，求出每组数据所构成的树的重心，输出这个树的重心的编号，并且输出重心删除后得到的最大子树的节点个数，如果个数相同取编号小的

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
//节点序号1~n
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;

struct Edge{
    int to,nex;
}e[N];

int n,tot;//节点的总数量和链式前向星的寄存指针
int siz[N],head[N],ans,pos;//s[]记录他在内的所有节点的个数,重心的最大子树节点数和重心的节点序号

void init(){
    ans=inf,pos=0;
    tot=0;
    memset(head,-1,sizeof head);
}

void add(int x,int y){
    tot++;
    e[tot].nex=head[x];
    head[x]=tot;
    e[tot].to=y;
}

void dfs(int x,int from){
    siz[x]=1;//因为是以x为根的整个树的大小所以算上自己
    int max_part=0;
    for(int i=head[x];~i;i=e[i].nex){
        int y=e[i].to;
        if (y==from)continue;
        dfs(y,x);
        siz[x]+=siz[y];
        max_part=max(max_part,siz[y]);//其孩子数量尝试作为最大子树
    }
    max_part=max(max_part,n-siz[x]);//其另一端（父亲）作为孩子尝试作为最大子树
    if(max_part<ans){//尝试更新答案
        ans=max_part,pos=x;
    }
}

signed main()
{
    int t;cin>>t;
    while(t--){
        init();
        cin>>n;
        for(int i=1;i<n;i++){//n-1条边
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
        dfs(1,0);//对于最初选定的根节点来说可以走遍左右的节点，所以父节点设为0
        cout<<pos<<" "<<ans<<endl;
    }   
    return 0;
}

带权节点常用模板

siz[i] 同上，dp[i] 表示以 i 为根节点的最大子树大小，val[i] 为 i 节点的点权

节点的点权影响了最大子树的选择，因为点权为 5 的点相当于 5 个点权为 1 的点，我们可以看成在节点位置及后面节点是 5 个完全相同的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//节点序号1~n
inline void dfs(int now,int from){
    siz[now]=val[now];//大小由看成val个权值为1的节点
    dp[now]=0;
    for(int i=head[now];i;i=a[i].nxt){
        int t=a[i].to;
        if(t==from) continue;
        dfs(t,now);
        siz[now]+=siz[t];
        dp[now]=max(dp[now],siz[t]);
    }
    dp[now]=max(dp[now],n-dp[now]);
    if(dp[now]<dp[ans]) pos=now//更新树的重心的节点序号
    //dp[]记录了每个节点作为重心的最大子树节点数:ans=dp[ans]
}

如果把权值数组 val[] 初始化为 1 那么就相当于无权节点找树的重心模板了

性质求解

一般来说定义求解就够用了，但在某些时候性质求解更方便实用，这里就以带权节点为例

根据性质2：我们可以处理出所有节点到某一节点的距离，取最小值

怎么求出每个节点到某一节点的距离呢？在 dfs 过程中向下处理是很容易的，所以我们可以先处理出所有节点到根节点的距离

siz[i] 同上，f[i] 表示节点 i 的所有子节点到i的距离和，val[i] 同上， a[i].val 为边权，设定 1 号节点为根节点

1
2
3
4
5
6
7
8
9
10
11
12
inline void dfs1(int now,int fa,int deep){
    siz[now]=val[now];
    dep[now]=deep;
    for(int i=head[now];i;i=a[i].nxt)
    {
        int t=a[i].to;
        if(t==fa)continue;
        dfs1(t,now,deep+a[i].val);
        siz[now]+=siz[t];
        f[now]+=f[t]+siz[t]*a[i].val;
    }
}

对于 f 数组的处理的理解：t 的所有子节点到 t 的距离 +now 的当前子树所有节点到 now 的距离。

这样就求得了根节点的距离和，我们再通过根节点递推其他节点的距离和，有如下公示：f[now]=f[from]+(siz[根]-2*siz[now])*边权;(now!=根节点)

对于 now 的子节点，每个节点的距离减少了一个边权，总距离减少 siz[now]*边权 ，对于非 v 子节点，每个节点距离增加了一个边权，总距离增加 (siz[根]-siz[now])*边权

1
2
3
4
5
6
7
8
9
inline void dfs2(int now,int fa){
    if(now^root) f[now]=f[fa]+siz[1]-2*siz[now];
    if(f[now]<sum) res=now,sum=f[now];
    for(int i=head[now];i;i=a[i].nxt){
        int t=a[i].to;
        if(t==fa)continue;
        dfs2(t,now); 
    }
}

这种方法还可以优化——观察式子：显然一个节点的所有子树中，只有子节点数最多的一个可能成为重心，所以我们可以加以改进，在 dfs2 中只走子树节点最多的一个

这样复杂度整体虽然还是 O(n) 的，但是查询复杂度变为了 O(树高) 在某些题目中(下面例题中)有奇效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void dfs1(int now,int fa,int deep){
    siz[now]=val[now];
    dep[now]=deep;
    int maxson=-1;//新 加 
    for(int i=head[now];i;i=a[i].nxt){
        int t=a[i].to;
        if(t==fa) continue;
        dfs1(t,now,deep+a[i].val);
        siz[now]+=siz[t];
        f[now]+=f[t]+siz[t]*a[i].val;
        if(siz[t]>maxson) maxson=siz[t],son[now]=t;//新加 
    }
}

inline void dfs2(int now,int fa){
    if(now^1) f[now]=f[fa]+siz[1]-2*siz[now];
    if(f[now]<sum) res=now,sum=f[now];
    if(son[now]) dfs2(t,now);//改动 
}

模板

模板题：第一行为 N ，1<N<=50000 ，表示树的节点数目，树的节点从 1 到 N 编号。 接下来 N-1 行，每行两个整数 U ，V ，表示 U 与 V 之间有一条边。 再接下 N 行，每行一个正整数，其中第 i 行的正整数表示编号为 i 的节点权值为 W(I) ，树的深度 <=100 。将最小的 S(x,y) 输出到 median.out ，结果保证不超过 1e9

先考虑暴力枚举 x ，y ，那么对于每一对 x ，y 分界都是一条树上的边。那么我们不如枚举断边，再找出重心。先 O(n) 求出 f[root] 的值，枚举断边，再通过上述第二种优化过的方法求距离和，总复杂度 O(N*树高) ，对于优化的处理：由于需要断边，每次断边后最大子树可能变小，所以我们需要维护一个次大子树

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
83
84
85
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;

inline ll read(){
    ll x=0,f=1;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') f=0,ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

ll n,res,cut;
ll val[100010],siz[100010],f[100010],dep[100010];
ll from[100010];
ll son1[100010],son2[100010];
ll head[100010],cnt=1;

struct poll{
    ll nxt,to;
}a[100010];
inline void add(ll x,ll y){
    a[++cnt].nxt=head[x];
    a[cnt].to=y;
    head[x]=cnt;
}
inline void dfs1(ll now,ll fa,ll deep){
    siz[now]=val[now];
    dep[now]=deep;
    from[now]=fa;
    for(ll i=head[now];i;i=a[i].nxt){
        ll t=a[i].to;
        if(t==fa) continue;
        dfs1(t,now,deep+1);
        siz[now]+=siz[t];
        f[now]+=(f[t]+siz[t]);
        if(siz[t]>siz[son1[now]]){
            son2[now]=son1[now];
            son1[now]=t;
        }
        else if(siz[t]>siz[son2[now]])
        son2[now]=t;
    }
}

inline void dfs3(ll now,ll sum,ll all,ll &ans){
    ans=min(ans,sum);
    ll t=son1[now];
    if(t==cut||siz[son2[now]]>siz[son1[now]]) t=son2[now];
    if(!t) return ;    
    if(2*siz[t]>all) dfs3(t,sum+all-2*siz[t],all,ans);
}
inline void dfs2(ll now){
    for(ll i=head[now];i;i=a[i].nxt){
        ll t=a[i].to;
        if(t==from[now])continue;
        cut=t;
        for(ll x=now;x;x=from[x]) siz[x]-=siz[t];
        ll A=inf,B=inf;
        dfs3(1,f[1]-f[t]-dep[t]*siz[t],siz[1],A);
        dfs3(t,f[t],siz[t],B);
        res=min(res,A+B);
        for(ll x=now;x;x=from[x]) siz[x]+=siz[t];
        dfs2(t);
    }
}

signed main()
{
    n=read();
    for(ll x,y,i=1;i<n;++i){
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    for(ll i=1;i<=n;++i)
    val[i]=read();
    res=inf;
    dfs1(1,0,0);
    dfs2(1);
    printf("%lld\n",res);
    return 0;
}

树的直径

参考博客

定义：我们将一棵树 T=(V,E) 的直径定义为 maxδ (u,v)(u,v∈V) ，也就是说，树中所有最短路径距离的最大值即为树的直径

以一道为讲解模板题：给一棵树，找出树的直径（即两点最短距离中最大的那条）

两次 DFS（或者 BFS ）求解

方法：建立无向图，先从任意一点P出发，找离它最远的点 Q ，再从点 Q 出发，找离它最远的点 W ，W 到 Q 的距离就是是的直径

简易证明：

从图中可以看出任选一个点 P 找到最远的 Q 一定是直径的一端，再从 Q 反向找最远的点则必定保证了是直径的另一端

详细证明：

  • 若 P 已经在直径上，根据树的直径的定义可知 Q 也在直径上且为直径的一个端点
  • 若 P 不在直径上，我们用反证法，假设此时 WQ 不是直径，AB 是直径

若 AB 与 PQ 有交点 C ，由于 P 到 Q 最远，那么 PC+CQ>PC+CA ，所以 CQ>CA ，易得 CQ+CB>CA+CB ，即 CQ+CB>AB ，与 AB 是直径矛盾不成立，如下图（其中 AB ，PQ 不一定是直线，画成直线是为了方便）

若 AB 与 PQ 没有交点， M 为 AB 上任意一点， N 为 PQ 上任意一点。首先还是 NP+NQ>NQ+MN+MB ，同时减掉 NQ ，得 NP>MN+MB ，易知 NP+MN>MB ，所以 NP+MN+MA>MB+MA ，即 NP+MN+MA>AB ，与 AB 是直径矛盾，所以这种情况也不成立，如下图

模板

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
#include<bits/stdc++.h>
using namespace std;
const int N=100005;//最大顶点数

int n,m,tot;//寄存指针
int q,ans;

int dis[N];//记录遍历的每个点到find()出发点的距离
int head[N],to[N],val[N],nex[N];//链式前向星非结构体

void init(){
    tot=0;
    memset(head,-1,sizeof head);
}

void add(int x,int y,int z){
	tot++;
	nex[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	val[tot]=z;
}

void dfs(int x,int from){
	if(ans<dis[x]){//更新最大距离
		ans=dis[x];
		q=x;
	}
	for(int i=head[x];~i;i=nex[i]){
		int j=to[i];
		if(j==from)continue;
		dis[j]=dis[x]+val[i];
		dfs(j,x);
	}
}

void find(int x){
	ans=0;
	dis[x]=0;
	dfs(x,0);
}

signed main()
{
	while(cin>>n>>m){//n各点m条边
        init();
        int x,y,z;char ch;//吃没用的方向字母
        for(int i=1;i<=m;++i){//加变
            cin>>x>>y>>z>>ch;
            add(x,y,z);add(y,x,z);
        }

        find(1);//选根节点为P寻找Q
        find(q);//从Q找W
        printf("%d\n",ans);//此时ans为树的直径
    }
	return 0;
}

树形DP求解

对于每个节点我们要记录两个值：

  • f1[i] 表示以 i为根的子树中，i到叶子结点距离的最大值

  • f2[i] 表示以 i 为根的子树中，i 到叶子结点距离的次大值

对于一个节点我们只用其子节点的 f1 更新它到叶子结点距离的最大值和次大值来保证两条路径完全不一样（或者说其子节点不会既在最长路径还在次大路径上）

若 j 是 i 的儿子，那么（下面的 w[i][j] 表示 i 到 j 的路径长度）:

  • 若 f1[i]<f1[j]+w[i][j] ，f2[i]=f1[i],f1[i]=f1[j]+w[i][j]
  • 否则若 f2[i]<f1[j]+w[i][j] ，f2 [i]=f1[j]+w[i][j]

这样做就是先看能否更新最大值，若能它的次大值就是原先的最大值，再更新它的最大值

若不能就看能不能更新次大值，若能就更新，不能就不管它

这样的话，最后的答案 ans=max{f1[i]+f2[i]} ，对于无向图任选一个节点作为根节点 i 然后不断用子节点 j 维护f1[i]和 f2[i] ，又因为找 f1[j] 和 f2[j] 和上述一样所以可以递归求解，对于有向图则需要找到根节点

模板

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
#include<bits/stdc++.h>
using namespace std;
const int N=100005;//最大节点数

int n,m;
int tot,ans;//寄存指针和答案

int f1[N],f2[N];

int head[N],to[N],val[N],nex[N];//链式前向星非结构体

void init(){
    tot=0;
    memset(head,-1,sizeof head);
}

void add(int x,int y,int z){
	tot++;
	nex[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	val[tot]=z;
}

void dp(int x,int from){
	for(int i=head[x];~i;i=nex[i]){//用所有的儿子节点尝试更新
		int j=to[i];
		if(j==from)continue;
		dp(j,x);//递归求解儿子节点

		if(f1[x]<f1[j]+val[i]){
			f2[x]=f1[x];
			f1[x]=f1[j]+val[i];
		}
		else if(f2[x]<f1[j]+val[i])
		f2[x]=f1[j]+val[i];

		ans=max(ans,f1[x]+f2[x]);//更新一次
	}
}

signed main()
{
	while(cin>>n>>m){
        init();
        int x,y,z;char ch;
        for(int i=1;i<=m;++i){
            cin>>x>>y>>z>>ch;
            add(x,y,z);
            add(y,x,z);
        }
        dp(1,0);
        printf("%d\n",ans);
    }
	return 0;
}

这俩做法差不多，两次 DFS 在效率和空间都要比树形 DP 表现的要好一点点差距不大

树链剖分

解决问题：树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息

分类：重链剖分、长链剖分和实链剖分

大多数情况下树链剖分就是指重链剖分，这里讲解也先只讲解重链剖分

重链剖分

引入：考虑一下两道题

  • 将树从 x 到 y 节点最短路径上所有节点的值就加上 z ——我们可以通过树上差分以 O(n+m) 复杂度解决
  • 求数从 x 到 y 节点最短路径上所有节点值之和——我们可以借助 LCA 解决，先 O(n) 预处理求出所有的节点到根节点的的距离 dis ，然后找到两节点的 LCA ，最后结果就是 dis[x]+dis[y]-dis[LCA] ，总的时间复杂度是 O(mlogn+n)

那么如果两个问题合并为同一个问题呢，每次执行操作一之后就必须重新预处理操作二的 dis ，即每次询问前都要再次 DFS 求 dis ，方法不够优秀

我们知道线段树是一种动态处理区间查询修改的线性结构，那么如果我们将树的节点分割成多条链然后利用线段树维护不就可以成功解决上述问题了吗？

当然根据情况不同可以使用其他数据结构来代替线段树解决其他相关问题

注意：重链剖分本质上是一种优化暴力的衍生算法

定义

  • 重子节点：表示其子节点中子树最大的子节点。如果有多个子树最大的子节点任取其一，如果没有子节点（即当前节点为叶节点）那么就无重子节点。注意：叶节点没有重儿子，非叶节点有且只有一个重儿子，显而易见的是若是某个节点没有重儿子就更不可能有轻儿子了

  • 轻子节点：刨去重子节点剩余的节点就是轻子节点

  • 重边：从这个节点到重子节点的边

  • 轻边：从这个节点到轻子节点的边

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链

操作

树剖的实现分两个 DFS 的过程：

  • 第一次 DFS 记录每个结点的父节点（ fa ）、深度（ dep ）、子树大小（ siz ）、重子节点（ son ）
  • 第二次 DFS 记录所在链的链顶（ top ，应初始化为结点本身）、重边优先遍历时的 DFS 序（ dfn ）、DFS 序对应的节点编号（ rnk ）
数组 意义
fa[x] 节点 x 在树上的父亲
dep[x] 节点 x 在树上的深度
siz[x] 节点 x 为根节点的树的节点个数（包括自己）
son[x] 节点 x 的重儿子
top[x] 节点 x 所在重链的顶部节点（深度最小）
dfn[x] 节点 x 的DFS序，也是其在线段树中的编号
rnk[x] DFS序所对应的节点编号，有 rnk(dfn(x))=x

具体实现

第一次 DFS 首先求出每个节点所在子树的大小，找到它的重儿子（借助求出的 siz 找并用 son 记录），同时顺便记录其父亲和深度（获得 fa[] 和 dep[] ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//节点序号1~n
void dfs1(int u,int from,int depth){//当前节点、父节点、层次深度
    fa[u]=from;
    dep[u]=depth;
    siz[u]=1;//这该节点本身就提供1个大小
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v==from)continue;
        dfs1(v,u,depth+1);//层次深度+1
        siz[u]+=siz[v];//子节点的siz已被处理，用它来更新父节点的siz
        if(siz[v]>siz[son[u]])
        son[u]=v;//选取siz最大的作为重儿子
    }
}

signed main()
{
    dfs1(root,0,1);//从根节点开始，其父节点选个不存在的0
}

第二次 DFS 连接出重链同时给每个节点标上 DFS 序，并且为了便于用其他数据结构来维护重链，我们在 DFS 时保证一条重链上各个节点 DFS 序连续（即优先遍历节点的重儿子在走其他的儿子）并获得 top[] 、dfn[] 和rnk[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//节点序号1~n
void dfs2(int u,int t){//当前节点序号、重链顶端节点序号
    top[u]=t;
    dfn[u]=++cnt;//标记dfs序
    rnk[cnt]=u;//序号cnt对应节点u
    if(!son[u])return ;//没有重儿子返还（轻儿子更没有了）
    dfs2(son[u],t);
    /*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
    一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])
        dfs2(v,v);//一个位于轻链底端的点，初始它的top必然是它本身
    }
}

性质

  • 树上每个节点都属于且仅属于一条重链
  • 重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）
  • 所有的重链将整棵树完全剖分
  • 在剖分时优先遍历重儿子 ，最后重链的DFS序就会是连续的
  • 在剖分时重边优先遍历 ，最后树的DFN序上，重链内的DFN序是连续的。按DFN序排序后的序列即为剖分后的链
  • 一颗子树内的DFN序是连续的
  • 可以发现，当我们向下经过一条轻边时，所在子树的大小至少会除以二，因此对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 O(logn) 次，因此树上的每条路径都可以被拆分称不超过 O(logn) 条重链

常见应用

因为树链剖分后可以获得多条线性的链并且链上的节点的DFN序是连续编号，所以我们可以按照节点的DFN序顺序存入线段树（或者树状数组）维护完成下述操作

路径上维护

  • 将树从 x 到 y 节点最短路径上所有节点值都加上 z
  • 查询树从 x 到 y 节点最短路径上所有节点值的加和

查询任意两点间路径和操作时：设所在链顶端的深度更深的那个点为 x 点

  • res 加上 x 点到 x 所在链顶端 这一段区间的点权和
  • 把 x 跳到 x 所在链顶端的那个点的上面一个点、

不断执行上述操作直到两个点处于同一条链上，这时再加上此时两个点的区间和即可（相当于是先分别计算两点所处不同链上路径和，在计算同一个链上经过的路径和）每次查询时间复杂度为 O(log2n)

1
2
3
4
5
6
7
8
9
10
11
12
int queryRange(int x,int y){
    int res=0;//计算器
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);//保证x是深度大的那个节点
        res+=query(1,dfn[top[x]],dfn[x]);//计算这一区间和
        x=fa[top[x]];//计算完向上跳到顶端的父节点（没计算的点）
    }
    if(dep[x]>dep[y])swap(x,y);//同一条链上深度小的dfn序小
    res+=query(1,dfn[x],dfn[y]);//计算最后一段区间和
    return res%mod;
}

更改操作和上述类似

1
2
3
4
5
6
7
8
9
10
void updateRange(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);//保证x是深度大的那个节点
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,dfn[x],dfn[y],z);
}

子树维护

  • 将以 x 为根节点的树内所有节点值都加上z
  • 查询以 x 为根节点的树内所有节点值的加和

和路径维护的操作一样，关键是如何确定修改的节点区间：因为 siz[] 记录了每个节点为根的树大小，并且其每个子树的DFN序都是连续的，所以修改区间为 [dfn[x],dfn[x]+siz[x]-1]

1
2
3
void updateSon(int x,int z){
    update(1,dfn[x],dfn[x]+siz[x]-1,z);
}

同理，查询操作和上述类似

1
2
3
int querySon(int x){
    return query(1,dfn[x],dfn[x]+siz[x]-1);
}

模板

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;//最大节点数

int n,m,root;//n个点m个询问，根节点
int tot,cnt;//链式前向星和DFS序的寄存指针
int a[maxn],head[maxn];//储存节点值和链式前向星的head
int fa[maxn],dep[maxn],siz[maxn],son[maxn];//第一次DFS用到的
int dfn[maxn],rnk[maxn],top[maxn];//第二次DFS用到的

struct Edge{
    int to,nex;
}e[maxn];

void init(){
    tot=cnt=0;
    memset(head,-1,sizeof head);
    memset(son,0,sizeof son);//必须初始化
}

void add(int x,int y){
    tot++;
    e[tot].nex=head[x];
    head[x]=tot;
    e[tot].to=y;
}

void dfs1(int u,int from,int depth){//当前节点、父节点、层次深度
    fa[u]=from;
    dep[u]=depth;
    siz[u]=1;//这该节点本身就提供1个大小
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v==from)continue;
        dfs1(v,u,depth+1);//层次深度+1
        siz[u]+=siz[v];//子节点的siz已被处理，用它来更新父节点的siz
        if(siz[v]>siz[son[u]])
        son[u]=v;//选取siz最大的作为重儿子
    }
}

void dfs2(int u,int t){//当前节点序号、重链顶端节点序号
    top[u]=t;
    dfn[u]=++cnt;//标记dfs序
    rnk[cnt]=u;//序号cnt对应节点u
    if(!son[u])return ;//没有重儿子返还（轻儿子更没有了）
    dfs2(son[u],t);
    /*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
    一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])
        dfs2(v,v);//一个点位于轻链底端，那么它的top必然是它本身
    }
}

//58~108行线段树模板(注意：存值按照DFN序存储)
struct segtree{
    int l,r;
    int val;
    int add;
}t[maxn<<2];

void build(int root,int l,int r){
	t[root].l=l,t[root].r=r,t[root].add=0;//关键：不初始化遇到跑多次就可能出错
	if(l==r){//递归基，区间不再划分 
		t[root].val=a[rnk[l]];//统计值 
		return ;//回退 
	}
	int mid=(l+r)>>1;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	t[root].val=t[root<<1].val+t[root<<1|1].val;//统计父节点答案
}

void spread(int p){//p是要更新节点的父元素 
	if(t[p].add){
		t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);//更新左子节点 
		t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);//更新右子节点
		t[p*2].add+=t[p].add;//下传延迟标记至左子节点 
		t[p*2+1].add+=t[p].add;//下穿延迟标记至右子节点 
		t[p].add=0;//清空父亲的延时标记 
	}
}

void update(int root,int l,int r,int x){
	if(l<=t[root].l&&r>=t[root].r){//递归基，无需划分问题的时候 
		t[root].val+=x*(t[root].r-t[root].l+1);//直接在和上添加答案 
		t[root].add+=x;//同时打上标记 
		return ;//返回		
	}
	spread(root);
	int mid=(t[root].l+t[root].r)/2;
	if(l<=mid)update(root*2,l,r,x);//左边小于右边，与左子节点有关 
	if(r>=mid+1)update(root*2+1,l,r,x);//右边比中点大，与右子节点有关 
	t[root].val=t[root*2].val+t[root*2+1].val;//更新父节点 
}

int query(int root,int l,int r){
	if(l<=t[root].l&&r>=t[root].r)//递归基，无需划分 
	return t[root].val;//直接返回
	spread(root);//下传延时标记 
	int mid=(t[root].l+t[root].r)>>1;//取中点
	int ans=0;
	if(l<=mid)ans+=query(root*2,l,r);
	if(r>=mid+1)ans+=query(root*2+1,l,r);
	return ans; 
}

//利用线段树维护操作
void updateRange(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,dfn[x],dfn[y],z);
}

int queryRange(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        res+=query(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res+=query(1,dfn[x],dfn[y]);
    return res;
}

void updateSon(int x,int z){
    update(1,dfn[x],dfn[x]+siz[x]-1,z);
}

int querySon(int x){
    return query(1,dfn[x],dfn[x]+siz[x]-1);
}

signed main()
{
    while(cin>>n>>m>>root){
        init();
        for(int i=1;i<=n;i++)cin>>a[i];//存储节点值
        for(int i=1;i<=n-1;i++){
            int x,y;cin>>x>>y;
            add(x,y),add(y,x);
        }
        
        dfs1(root,0,1);
        dfs2(root,root);
        build(1,1,n);
        
        int choice;
        while(m--){
            cin>>choice;
            if(choice==1){//路径修改
                int x,y,z;
                cin>>x>>y>>z;
                updateRange(x,y,z);
            }
            else if(choice==2){//路径查询
                int x,y;
                cin>>x>>y;
                cout<<queryRange(x,y)<<endl;
            }
            else if(choice==3){//子树修改
                int x,z;
                cin>>x>>z;
                updateSon(x,z);
            }
            else{//子树查询
                int x;cin>>x;
                cout<<querySon(x)<<endl;
            }
        }
    }
    return 0;
}

模板题：N 个节点组成的数，分别执行上述四种操作并将查询结果对 mod 取模

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<bits/stdc++.h>
#define ing long long int//卡int
using namespace std;
const int maxn=1e5+5;

int n,m,root,mod;//n个点m个询问，根节点和结果取模数
int tot,cnt;//链式前向星和DFS序的寄存指针
int a[maxn],head[maxn];//储存节点值和链式前向星的head
int fa[maxn],dep[maxn],siz[maxn],son[maxn];//第一次DFS用到的
int dfn[maxn],rnk[maxn],top[maxn];//第二次DFS用到的

struct Edge{
    int to,nex;
}e[maxn];

void init(){
    tot=cnt=0;
    memset(head,-1,sizeof head);
    memset(son,0,sizeof son);
}

void add(int x,int y){
    tot++;
    e[tot].nex=head[x];
    head[x]=tot;
    e[tot].to=y;
}

void dfs1(int u,int from,int depth){//当前节点、父节点、层次深度
    fa[u]=from;
    dep[u]=depth;
    siz[u]=1;//这该节点本身就提供1个大小
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v==from)continue;
        dfs1(v,u,depth+1);//层次深度+1
        siz[u]+=siz[v];//子节点的siz已被处理，用它来更新父节点的siz
        if(siz[v]>siz[son[u]])
        son[u]=v;//选取siz最大的作为重儿子
    }
}

void dfs2(int u,int t){//当前节点序号、重链顶端节点序号
    top[u]=t;
    dfn[u]=++cnt;//标记dfs序
    rnk[cnt]=u;//序号cnt对应节点u
    if(!son[u])return ;//没有重儿子返还（轻儿子更没有了）
    dfs2(son[u],t);
    /*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
    一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])
        dfs2(v,v);//一个点位于轻链底端，那么它的top必然是它本身
    }
}

struct segtree{
    int l,r;
    int val;
    int add;
}t[maxn<<2];

void build(int root,int l,int r){
	t[root].l=l,t[root].r=r,t[root].add=0;//关键：不初始化遇到跑多次就可能出错
	if(l==r){//递归基，区间不再划分 
		t[root].val=a[rnk[l]]%mod;//统计值 
		return ;//回退 
	}
	int mid=(l+r)>>1;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	t[root].val=t[root<<1].val+t[root<<1|1].val;//统计父节点答案
}

void spread(int p){//p是要更新节点的父元素 
	if(t[p].add){
		t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);//更新左子节点 
		t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);//更新右子节点
		t[p*2].add+=t[p].add;//下传延迟标记至左子节点 
		t[p*2+1].add+=t[p].add;//下穿延迟标记至右子节点 
		t[p].add=0;//清空父亲的延时标记 
	}
}

void update(int root,int l,int r,int x){
	if(l<=t[root].l&&r>=t[root].r){//递归基，无需划分问题的时候 
		t[root].val+=x*(t[root].r-t[root].l+1);//直接在和上添加答案 
		t[root].add+=x;//同时打上标记 
		return ;//返回		
	}
	spread(root);
	int mid=(t[root].l+t[root].r)/2;
	if(l<=mid)update(root*2,l,r,x);//左边小于右边，与左子节点有关 
	if(r>=mid+1)update(root*2+1,l,r,x);//右边比中点大，与右子节点有关 
	t[root].val=t[root*2].val+t[root*2+1].val;//更新父节点 
}

int query(int root,int l,int r){
	if(l<=t[root].l&&r>=t[root].r)//递归基，无需划分 
	return t[root].val;//直接返回
	spread(root);//下传延时标记 
	int mid=(t[root].l+t[root].r)>>1;//取中点
	int ans=0;
	if(l<=mid)ans+=query(root*2,l,r);
	if(r>=mid+1)ans+=query(root*2+1,l,r);
	return ans; 
}

void updateRange(int x,int y,int z){
    z%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,dfn[x],dfn[y],z);
}

int queryRange(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        res+=query(1,dfn[top[x]],dfn[x]);
        res%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res+=query(1,dfn[x],dfn[y]);
    return res%mod;
}

void updateSon(int x,int z){
    update(1,dfn[x],dfn[x]+siz[x]-1,z);
}

int querySon(int x){
    return query(1,dfn[x],dfn[x]+siz[x]-1)%mod;
}

signed main()
{
    while(cin>>n>>m>>root>>mod){
        init();
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n-1;i++){
            int x,y;cin>>x>>y;
            add(x,y),add(y,x);
        }
        dfs1(root,0,1);
        dfs2(root,root);
        build(1,1,n);
        int choice;
        while(m--){
            cin>>choice;
            if(choice==1){
                int x,y,z;
                cin>>x>>y>>z;
                updateRange(x,y,z);
            }
            else if(choice==2){
                int x,y;
                cin>>x>>y;
                cout<<queryRange(x,y)<<endl;
            }
            else if(choice==3){
                int x,z;
                cin>>x>>z;
                updateSon(x,z);
            }
            else{
                int x;cin>>x;
                cout<<querySon(x)<<endl;
            }
        }
    }
    return 0;
}

求最近公共祖先

因为树链剖分也得到了DFN序，所以也可以顺便求出任意连点的 LCA ：不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA ，向上跳重链时需要先跳所在重链顶端深度较大的那个

要是树链剖分的题有问到可以直接用，要是只是求个 LCA 倍增算法和 Tarjan 算法足矣

1
2
3
4
5
6
7
8
int LCA(int u,int v) {
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])
        u=fa[top[u]];
        else v=fa[top[v]];
    }
  return dep[u]>dep[v]?v:u;
}

长链剖分

  • [ ] 待整理