2020-2021:teams:wangzai_milk:树链剖分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 14:33] infinity37 [怎么剖] |
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:22] (当前版本) infinity37 [怎么剖] |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| ==== 怎么剖 ==== | ==== 怎么剖 ==== | ||
| - | 所谓的树链剖分其实也就是将一颗树的所有边分为轻链和重链两个部分。 | + | 所谓的树链剖分其实也就是将一颗树的所有边分为轻链和重链两个部分。剖分效果如图。 |
| - | 树链剖分要经过两次深搜，第一次深搜以某个节点为根开始深搜得到每个点的重儿子。第二次深搜要维护每个点的$top$，其代码如下。 | + | {{:2020-2021:teams:wangzai_milk:树链剖分-sample1.png?400|}} |
| + | |||
| + | 树链剖分要经过两次深搜。 | ||
| + | 第一次深搜以某个节点为根开始深搜得到每个点的重儿子，具体流程为统计每个儿子的$size$，保留其中$size$最大的为重儿子，与此同时确定一的点的父亲，$size$以及其深度。 | ||
| <code c++> | <code c++> | ||
| 行 35: | 行 38: | ||
| } | } | ||
| } | } | ||
| + | </code> | ||
| + | 第二次深搜要维护每个点的$top$，首先根节点的$top$是其本身，对于一个点，如果该点有重儿子，那么优先索其重儿子，而其重儿子的$top$也就是该点的top，对于其他儿子，其$top$就是儿子自身。 | ||
| + | <code c++> | ||
| void dfs2(int u,int t) | void dfs2(int u,int t) | ||
| { | { | ||
| - | sz++,pos[u]=sz; | + | top[u]=t; |
| - | inv[sz]=u,top[u]=t; | + | |
| if(son[u])dfs2(son[u],t); | if(son[u])dfs2(son[u],t); | ||
| for(int i=head[u];~i;i=Edges[i].next) | for(int i=head[u];~i;i=Edges[i].next) | ||
| 行 58: | 行 63: | ||
| if (dep[top[x]]<dep[top[y]])swap(x,y); | if (dep[top[x]]<dep[top[y]])swap(x,y); | ||
| query(num[top[x]],num[x]); | query(num[top[x]],num[x]); | ||
| - | x = fa[top[x]]; | + | x = father[top[x]]; |
| } | } | ||
| if (dep[x]<dep[y])swap(x,y); | if (dep[x]<dep[y])swap(x,y); | ||
| 行 66: | 行 71: | ||
| 那么这样剖分并查询为什么时间复杂度是$O(logn)$的呢，首先dfs的时候优先处理每个点的重儿子，那么一条重链在dfs序列中式一段连续的区间。我们在查询的时候，每次跳到$top$的父亲都会走一条轻边，可以发现$fa_{top_x}$的$size$至少是$top_x$的$size$的二倍，那么我们最多跳转了$log(n)$次就会结束查询。 | 那么这样剖分并查询为什么时间复杂度是$O(logn)$的呢，首先dfs的时候优先处理每个点的重儿子，那么一条重链在dfs序列中式一段连续的区间。我们在查询的时候，每次跳到$top$的父亲都会走一条轻边，可以发现$fa_{top_x}$的$size$至少是$top_x$的$size$的二倍，那么我们最多跳转了$log(n)$次就会结束查询。 | ||
| + | |||
| + | 通常树链剖分算法会和线段树相结合。 | ||
| ===== 怎么用 ===== | ===== 怎么用 ===== | ||
2020-2021/teams/wangzai_milk/树链剖分.1591338812.txt.gz · 最后更改: 2020/06/05 14:33 由 infinity37
