纯循环 DFS

在做 P5384 Cnoi2019雪松果树 的时候无聊玩出来的无用科技。

众所周知，有一类题目会通过给出 的方式来给出一棵树，并且有 这样的很好的性质。

所以不妨考虑如何不使用递归或栈来 DFS 这样的一棵树。

首先我们既然需要 DFS 而非 BFS，那么基本都是需要 DFS 序的，所以我们先求出这个。

考虑这样的情况：

1
2
3
4
5
6
7
graph TD
    1((1)) --> 2((2))
    1 --> 3((3))
    1 --> 4((4))
    2 --> 5{...}
    3 --> 6{...}
    4 --> 7{...}

假定我们按照编号从小到大的顺序遍历三个点，那么 且 ，原因显然。

那么我们在读入 之后倒序遍历 个点，每个点向父亲贡献 ，同时如果父亲 非零则说明其已经“遍历”了一些儿子，此时我们的 DFS 序应该是父亲的 DFS 序加上其当前 ，我们将这个值先存在 里面。

然后再顺序扫一遍，然后将 设为 ，然后每个点的 DFS 序加上其父亲的 DFS 序即可，并将每个 DFS 序对应的结点编号记做 。

DFS 这棵树按照 的顺序遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=2;i<=n;++i){
    read(fa[i]);
    dp[i]=dp[fa[i]]+1;
}
for(int i=n;i>1;--i){
    dfn[i]=sz[fa[i]]+1;
    sz[fa[i]]+=++sz[i];
}
++sz[1];
for(int i=dfn[1]=1;i<=n;++i)
    rk[dfn[i]+=dfn[fa[i]]]=i;

// 然后 DFS 一遍
for(int i=1;i<=n;++i){
    int x=rk[i];
    // ...
}

树链剖分

那么我们考虑支持一下最常见的应用。

树剖的话，那么变化就是我们要将某个儿子的 DFS 序减小，然后将一些儿子的 DFS 序增大。

显然这个被减小的 DFS 序的结点编号必须大于这个重儿子。

所以也很显然：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=2;i<=n;++i){
    read(fa[i]);
    dp[i]=dp[fa[i]]+1;
}
for(int i=n;i>1;--i){
    dfn[i]=sz[fa[i]]+1;
    sz[fa[i]]+=++sz[i];
    if(sz[hs[fa[i]]]<sz[i]) hs[fa[i]]=i;  // 更新重儿子
}
++sz[1];
for(int i=dfn[1]=1;i<=n;++i){
    if(i!=hs[fa[i]]){
        dfn[i]+=dfn[fa[i]];  // 不是重儿子
        if(i>hs[fa[i]]) dfn[i]+=sz[hs[fa[i]]];  // DFS 序增大
        tp[i]=i;
    }else{
        dfn[i]=dfn[fa[i]]+1;  // 是重儿子
        tp[i]=tp[fa[i]];
    }
    rk[dfn[i]]=i;
}
≡