/ Vijos / 讨论 / 问答 /

树的dfn序

本人初一,刚学“树链剖分”,觉得 \(dfn\)序是个玄学的东西

那么:

\(dfn\)序到底指的是什么?

本人 ~~***太弱***~~ 实在是搜了百度也没有得到客观的结果。望大佬 解答啊!

1 条评论

  • @ 2019-08-25 16:37:54

    我认为,**所谓的\(dfn\)序** 其实就是在 树链剖分 的过程中 访问节点的顺序。

    是这样的吗?

    • @ 2019-09-20 22:25:33

      是的,通常树链剖分是这样,以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);
          }
      }
      
    • @ 2019-09-20 22:26:48

      你可以看这个

  • 1