- 问答
- 2019-08-25 16:27:09 @
本人初一,刚学“树链剖分”,觉得 \(dfn\)序是个玄学的东西
那么:
\(dfn\)序到底指的是什么?
本人 ~~***太弱***~~ 实在是搜了百度也没有得到客观的结果。望大佬 解答啊!
1 条评论
-
bfw (bfw) LV 8 @ 2019-08-25 16:37:54
我认为,**所谓的\(dfn\)序** 其实就是在 树链剖分 的过程中 访问节点的顺序。
是这样的吗?
- 1
本人初一,刚学“树链剖分”,觉得 \(dfn\)序是个玄学的东西
那么:
\(dfn\)序到底指的是什么?
本人 ~~***太弱***~~ 实在是搜了百度也没有得到客观的结果。望大佬 解答啊!
我认为,**所谓的\(dfn\)序** 其实就是在 树链剖分 的过程中 访问节点的顺序。
是这样的吗?
是的,通常树链剖分是这样,以luogu树剖模板为例
void dfs1 (int x)
{
vertex[x].size = 1;
for(register int now = vertex[x].head; now; now = edge[now].link)
{
register int v = edge[now].to;
if(v == vertex[x].f)
continue;
vertex[v].f = x;
vertex[v].deep = vertex[x].deep + 1;
dfs1(v);
vertex[x].size += vertex[v].size;
if(vertex[v].size > vertex[vertex[x].son].size)
vertex[x].son = v;
}
}
void dfs2 (int x, int y)
{
vertex[x].top = y;
vertex[x].id = ++tot;
add_tree(1,1,n,vertex[x].id,vertex[x].id,vertex[x].value);
if(vertex[x].son)
dfs2(vertex[x].son, y);
for(register int now = vertex[x].head; now; now = edge[now].link)
{
register int v = edge[now].to;
if(v == vertex[x].f)
continue;
if(v == vertex[x].son)
continue;
dfs2(v, v);
}
}
你可以看这个