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

讲讲一些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.starroad.top/archives/422.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！