不知不觉间，暑假就过去了一半，我还是个垃圾。

讲讲一些DFS序列相关的问题，本质就是把树扯成一个线性的结构。

在DFS的过程中，L[u]和R[u]表示节点第一次访问到u的时间和离开u的时间，这样我们要对u的子树进行信息维护时就可以直接维护序列L[u]到R[u]这连续的一段。

代码如下：

void dfs( int u, int fa ) {
    L[u] = ++dfs_clock;
    for ( int i = head[u]; i; i = e[i].next ) {
        int v = e[i].v;
        if ( v == fa )
            continue;
        dfs( v, u );
    }
    R[u] = dfs_clock;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/422.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。