2020-2021:teams:wangzai_milk:树链剖分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:20] infinity37 [怎么剖] |
2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:22] (当前版本) infinity37 [怎么剖] |
||
|---|---|---|---|
| 行 39: | 行 39: | ||
| } | } | ||
| </code> | </code> | ||
| - | 第二次深搜要维护每个点的$top$，首先根节点的$top$是其本身，对于一个点，如果该点有重儿子，那么有限搜索其重儿子，而其重儿子的$top$也就是该点的top，对于其他儿子，其$top$就是儿子自身。 | + | 第二次深搜要维护每个点的$top$，首先根节点的$top$是其本身，对于一个点，如果该点有重儿子，那么优先索其重儿子，而其重儿子的$top$也就是该点的top，对于其他儿子，其$top$就是儿子自身。 |
| <code c++> | <code c++> | ||
| void dfs2(int u,int t) | void dfs2(int u,int t) | ||
| 行 63: | 行 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/树链剖分.1591341606.txt.gz · 最后更改: 2020/06/05 15:20 由 infinity37
