2020-2021:teams:wangzai_milk:树链剖分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 14:34] 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); | ||
2020-2021/teams/wangzai_milk/树链剖分.1591338877.txt.gz · 最后更改: 2020/06/05 14:34 由 infinity37
