一个网站开发流程图,建设网站用模版,阿里建站服务,建湖做网站哪家最好本篇博客参考#xff1a;
【洛谷日报#17】树链剖分详解Oi Wiki 树链剖分 文章目录 基本概念代码实现常见应用路径维护#xff1a;求树上两点路径权值和路径维护#xff1a;改变两点最短路径上的所有点的权值求最近公共祖先 基本概念
首先#xff0c;树链剖分是什么呢
【洛谷日报#17】树链剖分详解Oi Wiki 树链剖分 文章目录 基本概念代码实现常见应用路径维护求树上两点路径权值和路径维护改变两点最短路径上的所有点的权值求最近公共祖先 基本概念
首先树链剖分是什么呢
简单来说就是把一棵树分成很多条链然后利用数据结构线段树、树状数组维护链上的信息
下面是一些定义
重子结点父亲结点的所有儿子结点中子树结点数目最多的结点称为重子结点轻子结点父亲结点的所有儿子中除了重子结点的其他结点称为轻子结点
如果某个结点是叶子结点那么它既没有重子结点也没有轻子结点
重边父亲结点和重子结点连成的边轻边父亲结点和轻子结点连成的边重链多条重边连接成的链轻链多条轻边连接成的链
落单的点也当做重链那整棵树就会被分成若干条重链类似这样图源Oi Wiki 下面是一些变量声明
fa[u] 结点 u 的父亲结点dep[u] 结点 u 的深度sz[u] 以结点 u 为根的子树的结点个数son[u] 结点 u 的重儿子top[u] 结点 u 所在链的顶端结点dfn[u] 结点 u 在 dfs 中的执行顺序同时也是树链剖分后的新编号可以理解为dfs序的映射id[u] dfn 标号 u 对应的结点编号有 id[dfn[u]] u
树链剖分的一些性质
重链开头的结点不一定是重子结点因为每一个非叶子结点不管是重子结点还是轻子结点都有重边剖分时重链优先遍历最后的 dfs 序中也就是 dfn 数组重链的 dfs 序时连续的按 dfs 序排序后的序列就是剖分后的链时间复杂度 O ( l o g n ) O(logn) O(logn)
代码实现
接下来需要实现树链剖分也就是把每个结点划到一条链里这通常是由两边 dfs 来实现的
第一遍 dfs
目的处理 fa[u] dep[u] sz[u] son[u]
void dfs1(int u, int father, int depth) // u: 当前结点 fa: 父结点 depth: 当前深度
{fa[u] father; // 更新当前结点父结点dep[u] depth; // 更新当前结点深度sz[u] 1; // 子树大小初始化为1for (int i 0; i g[u].size(); i ){int j g[u][i]; // 子结点编号if (j father) continue;dfs1(j, u, depth 1);sz[u] sz[j]; // 用子结点的sz更新父结点的szif (sz[j] sz[son[u]]) son[u] j; // 更新重子结点}
}第二遍 dfs
目的处理 top[u] dfn[u] id[u]
void dfs2(int u, int tt) // u: 当前结点 tt: 重链顶端结点
{top[u] tt; // 更新当前结点所在重链顶端dfn[u] cnt; // 更新dfs序id[cnt] u; // 更新dfs序的映射if (!son[u]) return; // 叶子结点 直接退出// 优先遍历重子结点 目的是保证链上各个结点的dfs序连续// 当前结点的重子结点和当前结点在同一条链上 所以链的顶端都是ttdfs2(son[u], tt); for (int i 0; i g[u].size(); i ){int j g[u][i]; // 子结点编号if (j son[u] || j fa[u]) continue; // 遇到重子结点或者父结点就跳过dfs2(j, j); // j点位于轻链顶端 它的top必然是本身}
}常见应用
两遍 dfs 之后就已经完成了树链剖分的操作但是由于本人举一反三能力缺失根本不知道应该怎么用所以后面再放几个常见的使用情况
路径维护求树上两点路径权值和
这里做的是一个类似LCA的操作如果两个结点不在同一条链上就让深度更大的结点往上跳每次只能跳一个结点避免两个结点一起跳导致擦肩而过直到跳到同一条链上因为同一条链上的点 dfs 序是相邻的所以可以直接在这条链上用数据结构计算权值和下面的代码用的是线段树
int sum(int x, int y) // xy表示待求的两点路径权值和
{int ans 0;int tx top[x], ty top[y]; // tx ty分别表示x和y所在重链的顶端结点while (tx ! ty) // 让x和y跳到同一条链上{if (dep[x] dep[y]) // x比y更深 让x先跳{ans query(dfn[tx], dfn[x]); // query是线段树的区间求和函数x fa[tx], tx top[x]; // 让x跳到原先链顶端的父结点 更新tx}else{ ans query(dfn[ty], dfn[y]); // query是线段树的区间求和函数y fa[ty], ty top[y]; // 让y跳到原先链顶端的父结点 更新ty}}// 循环结束 x和y终于到了同一条链 但是二者不一定是同一个结点 所以还需要计算两点之间的贡献if (dfn[x] dfn[y]) ans query(dfn[x], dfn[y]);else ans query(dfn[y], dfn[x]);return ans;
}路径维护改变两点最短路径上的所有点的权值
和上面的求最短路径权值和很像都是先让两个点跳到同一条链上再进行计算
void update(int x, int y, int c) // 把x与y的最短路上所有点的权值都加上c
{int tx top[x], ty top[y];while (tx ! ty){if (dep[tx] dep[ty]){modify(dfn[tx], dfn[x], c); // modify是线段树区间修改的函数x fa[tx], tx top[x]; // 让x跳到原先链顶端的父结点 更新tx}else{modify(dfn[ty], dfn[y], c); // modify是线段树区间修改的函数y fa[ty], ty top[y]; // 让y跳到原先链顶端的父结点 更新ty}}// 循环结束 x和y终于到了同一条链 但是二者不一定是同一个结点 所以还需要对两点之间的结点进行修改if (dfn[x] dfn[y]) modify(dfn[x], dfn[y], c);else modify(dfn[y], dfn[x], c);
}求最近公共祖先
思路就是如果两个点不在一条重链上那就不断让深度大的结点往上跳直到跳到同一条链上那么深度较小的点就是LCA
int lca(int u, int v) // 求u和v的lca
{while (top[u] ! top[v]) // 如果u和v不在同一条链上就一直让深度大的点往上跳{if (dep[top[u]] dep[top[v]]) u fa[top[u]];else v fa[top[v]];}return dep[u] dep[v] ? v : u; // 深度小的结点就是lca
}
