2020-2021:teams:wangzai_milk:树链剖分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:12] infinity37 [怎么剖] |
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:22] (当前版本) infinity37 [怎么剖] |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| {{:2020-2021:teams:wangzai_milk:树链剖分-sample1.png?400|}} | {{:2020-2021:teams:wangzai_milk:树链剖分-sample1.png?400|}} | ||
| - | 树链剖分要经过两次深搜，第一次深搜以某个节点为根开始深搜得到每个点的重儿子。第二次深搜要维护每个点的$top$，其代码如下。 | + | 树链剖分要经过两次深搜。 |
| + | 第一次深搜以某个节点为根开始深搜得到每个点的重儿子，具体流程为统计每个儿子的$size$，保留其中$size$最大的为重儿子，与此同时确定一的点的父亲，$size$以及其深度。 | ||
| <code c++> | <code c++> | ||
| 行 37: | 行 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) | ||
| 行 60: | 行 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/树链剖分.1591341125.txt.gz · 最后更改: 2020/06/05 15:12 由 infinity37
