gis网站开发教程,上海企业网上公示官网,广州手机软件开发,wordpress头部标签描述我们经常会遇到树的问题#xff0c;但树是非线性的结构#xff0c;操作起来始终还是麻烦#xff0c;如果我们能把树改造成线性结构#xff0c;有什么方法#xff1f;对#xff0c;就是今天要讲的DSF序#xff1b; dfs序呢#xff0c;就是把一棵树区间化#xff0c;我们…我们经常会遇到树的问题但树是非线性的结构操作起来始终还是麻烦如果我们能把树改造成线性结构有什么方法对就是今天要讲的DSF序 dfs序呢就是把一棵树区间化我们用dfs的方式将它区间化。 如图 dfs序就是ABDDEEBCFHHFG 其实就是用dfs全部遍历一遍不过我们不能光遍历还有动些小手脚我们要在遍历的同时记录每个节点进栈与出栈的时间序列。
介绍两个基本函数in[x],out[x] dfs从根节点开始这俩函数就分别记录每个节点x进入与离开的时间戳 还有num[x]表示第x个节点的编号
inline int dfs(int x,int fa,int time)
{in[x]time;num[time]x;for(int i1;ie[x].size();i){int we[x][i];if(wfa)continue;//防止又从子节点找回去dfs(w,x,time); }out[x]time;
} dfs(s,0,0);具体情况根据根据题目来写 num生成的就是一个新秩序由每个节点进入关系而形成的 你仔细观察会发现 序根节点的进栈时间子树的dfs根节点的出栈时间 这样不就成一个区间了 in[x]~out[x]是x为根节点的子树划分为一个区间 然后什么单点修改区间查询莫队都可以用在树上而且dfs序也是树链剖分的前驱知识
光说可能不怎么懂我去找一些题做完再更新例题
