DFS序总结

标签: -----------算法总结-------------

DFS序

对树进行dfsdfs遍历,所形成的序列就叫做树的dfsdfs序。
DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们就可以将树形结构转化为线性结构 处理。

int in[N],ou[N];
int idx;int b[N];
void dfs(int x,int fa){
    in[x] = ++ idx;
    b[idx] = x;
    for(int i = head[x];i;i = edge[i].next){
        int y = edge[i].to;
        if(y == fa) continue;
        dfs(x,y);
    }
    ou[x] = idx;
}

欧拉序

以下转自Pealicx
树的欧拉序是对树进行DFS的一种序列。有两种形式:1、在每个结点进和出都加进序列。2、只要到达每一个结点就把他加进序列。

例如:给出一棵树:

在这里插入图片描述

第一种方法得到的序列和对应的进出状态分别是:

1 2 3 3 4 4 5 5 2 6 7 7 8 8 6 1

进 进 进 出 进 出 进 出 出 进 进 出 进 出 出 出

(每个结点恰好出现了两次)

用这个序列可以解决树上求和的问题:

1、求某个点到根节点的点权值和。方法是:需要在进的点处做加法,出的点处做减法,查询某点就只需要查询对应的前缀即可。

*2、求某个子树的权值和。方法是:需要在进的点处做加法,求某个点最后一次出现的位置的前缀和减去第一次出现的位置的前一个位置的前缀和即可。

第二种方法得到的序列是:

1 2 3 2 4 2 5 2 1 6 7 6 8 6 1

用这一个序列,可以解决的一个问题是:

1、求某两点的LCA。显然这两点之间的区间中,深度最小点就是LCA。这可以用RMQ解决。

2、求某个子树的权值和,方法是:只记录第一次出现的数的值,同样的查询某点就只需要查询该点在欧拉序中最后出现的位置的前缀即可减去第一次出现的额位置-1的前缀和即可。

3、换根操作:这种欧拉序相当于以根为起点围着树跑了一圈,那么我们就可以把欧拉序写成一个环就是:

1 2 3 2 4 2 5 2 1 6 7 6 8 6 1 2 3 2 4 2 5 2 1 6 7 6 8 6

以某个点为跟的欧拉序就是以某个点在上面的欧拉序中第一次出现的位置为起点向前走(2*n-1)步,例如以4为根的欧拉序就是

1 2 3 2 4 2 5 2 1 6 7 6 8 6 1 2 3 2 4 2 5 2 1 6 7 6 8 6

    \ \\ \ \ \ \qquadL-------------------------------------------------R//以4为跟的欧拉序,同时可以维护和之类的东西。

int in[N],ou[N];
int idx;int b[N];
void dfs(int x,int fa){
    in[x] = ++idx;
    b[idx] = x;
    vis[idx] = 0;//标记入点
    for(int i = head[x];i;i = edge[i].next){
        int y = edge[i].to;
        if(y == fa) continue;
        dfs(y,x);
    }
    ou[x] = ++idx;
    b[idx] = x;
    vis[idx] = 1;//标记出点
}

bzoj4034: [HAOI2015]树上操作
在这里插入图片描述
思路:
欧拉序维护到根的点权和。在入点加,出点减。这样,求某个节点到根路径上的点权和时,直接对区间[1,in[x]][1,in[x]]求和即可。而1,2操作其实就是区间加。
因为有对区加的修改,所以我们可定要用懒标记,可是一个区间中入点是正的,出点是负的,我们进行区间修改时似乎没法操作。那么我们在引入cnt[i]cnt[i],表示ii节点所代表的区间中有多少个出点(负)。那么区间修改,就是当前节点 加上 (rl+12cnt[rt])lzy[rt](r-l+1 - 2*cnt[rt])\cdot lzy[rt],为什么要减去二倍呢,是以为负的有cnt[rt]cnt[rt]个,那么正的就是rl+1cnt[rt]r-l+1-cnt[rt]个,然后两者做差就是区间的增量了。这里debug好大会。。。。一定要注意。同理,懒标记的下放也是如此。

struct Edge
{
    int next;
    int to;
}edge[N<<1];
int head[N],tot;
int in[N],ou[N];
ll a[N],b[N];bool vis[N];
inline void add(int from,int to ){
    edge[++tot].next = head[from];
    edge[tot].to = to;
    head[from] = tot;
}
ll tree[N<<2];int cnt[N<<2];ll lzy[N<<2];
inline void push_down(int rt,int len){
    tree[rt<<1] += 1LL*(len-(len>>1)-2*cnt[rt<<1])*lzy[rt];
    lzy[rt<<1] += lzy[rt];
    tree[rt<<1|1] += 1LL*((len>>1) - 2*cnt[rt<<1|1])*lzy[rt];
    lzy[rt<<1|1] += lzy[rt];
    lzy[rt] = 0;
}
void built(int rt,int l,int r){
    if(l == r) {
        if(vis[l]) tree[rt] = -a[b[l]],cnt[rt] ++;
        else tree[rt] = a[b[l]];
        return ;
    }
    int mid = l + r >> 1;
    built(rt<<1,l,mid);
    built(rt<<1|1,mid+1,r);
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
    cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
}
int idx;
void dfs(int x,int fa){
    in[x] = ++idx;
    b[idx] = x;
    vis[idx] = 0;//标记入点
    for(int i = head[x];i;i = edge[i].next){
        int y = edge[i].to;
        if(y == fa) continue;
        dfs(y,x);
    }
    ou[x] = ++idx;
    b[idx] = x;
    vis[idx] = 1;//标记出点
}
void update(int L,int R,int dat,int rt,int l,int r){
    if(L<=l&&r<=R){
        tree[rt] += 1LL*(r-l+1 - 2*cnt[rt])*dat;
        lzy[rt] += dat;
        return ;
    }
    if(lzy[rt]) push_down(rt,r-l+1);
    int mid = l + r >> 1;
    if(L <= mid) update(L,R,dat,rt<<1,l,mid);
    if(R>mid) update(L,R,dat,rt<<1|1,mid + 1,r);
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
ll query(int L,int R,int rt,int l,int r){
    if(L<=l&&r<=R){
        return tree[rt];
    }
    if(lzy[rt]) push_down(rt,r-l+1);
    int mid = l + r >> 1;
    ll ans = 0;
    if(L <= mid) ans += query(L,R,rt<<1,l,mid);
    if(R>mid) ans += query(L,R,rt<<1|1,mid+1,r);
    return ans;
}
int main(){
    int n,m;
    n = read(),m = read();
    rep(i,1,n) a[i] = read();
    rep(i,1,n-1) {
        int u = read(),v = read();
        add(u,v);
        add(v,u);
    }
    dfs(1,0);//预处理欧拉序
    built(1,1,idx);
    rep(i,1,m){
        int op = read();
        if(op == 1){
            int p = read(),d = read();
            update(in[p],in[p],d,1,1,idx);
            update(ou[p],ou[p],d,1,1,idx);
        }
        else if(op==2){
            int p = read(),d = read();
            update(in[p],ou[p],d,1,1,idx);
        }
        else {
            int p = read();
            printf("%lld\n",query(1,in[p],1,1,idx));
        }
    }

}

版权声明:本文为qq_43408238原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43408238/article/details/105224898

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...