Loading... 不知不觉间，暑假就过去了一半，我还是个垃圾。 <!--more--> 讲讲一些`DFS序列`相关的问题，本质就是把树扯成一个线性的结构。 <div class="tip inlineBlock share"> DFS序就是指一棵树被dfs时所经过的节点的顺序。DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段。 </div> 在DFS的过程中，L[u]和R[u]表示节点第一次访问到u的时间和离开u的时间，这样我们要对u的子树进行信息维护时就可以直接维护序列L[u]到R[u]这连续的一段。 代码如下： ```cpp 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; } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/422.html">https://www.starroad.top/archives/422.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：July 24th, 2019 at 08:48 pm © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
