树链剖分

Fri Apr 11 2025 09:15:58 GMT+0800

算法目的

维护静态树上的路径信息

算法流程

分两次DFS预处理出以下关键值：

DFS	值	含义	获得方式
1	father[x]	x在树中的父亲	在dfs传参中获得
1	dep[x]	x在树中的深度	在dfs传参中获得
1	size[x]	x为根的子树大小	在dfs传递归中获得
1	son[x]	x的重儿子编号	在dfs传递归中获得
2	top[x]	x所在的重路径的顶部结点编号	top[重儿子]=top[自己] top[轻儿子]=轻儿子
2	seg[x]	x在线段树中的位置	按照先访问重儿子的顺序先序遍历树，使得每条重链上的节点在线段树上保持相邻
2	rev[y]	y在树中的结点编号	这个简单

线段树的建树和查询的实现就只需按一般的做法

树链的查询

void ask (int x, int y)
{
    int fx = top[x],fy = top[y];
    while(fx != fy)							//直到两个点在同一条重链上
    {
        if(dep[fx] < dep[fy]) 				//选择深度大的往上跳
            swap(x, y),swap(fx, fy);
        query(1, 1, seg[0], seg[fx], seg[x]);	
        x = father[fx]; fx=top[x];
    }
    if(dep[x] > dep[y]) 					//先序遍历导致：在同一棵子树上深度大的点在线段树中的位置靠后
        swap(x, y);
    query(1, 1, seg[0], seg[x], seg[y])		//而seg[x]<=seg[y]故dep[x]<=dep[y]
}