精华内容
下载资源
问答
  • LibreOJ-dfs序2 (dfs序,线段树) 题目描述 给一棵有根树,这棵树由编号为1~N 的 N个结点组成。根结点的编号为R。每个结点都有一个权值,结点 的权值为 。 接下来有 M组操作,操作分为两类: 1 a x,表示将结点 的子...
  • 树的DFS序及其应用

    2017-10-20 14:23:43
    适用于正在搞OI的选手学习和提高,一种很不错的思想,近年来NOIP考察树上的东西渐多,值得好好学习
  • 关于算法竞赛中DFS序的有关资料与用途总结,对于NOIP选手及CSM选手有较大的帮助,可以考虑下载,有助于理解掌握DFS序
  • dfs序

    2018-10-19 20:40:16
    dfs序 tree数组为线段树,len为线段树长度,lazy为懒惰数组 #include <bits/stdc++.h> using namespace std; const int maxn = 5e4+7; int n,m; vector<int> adj[maxn]; int len...

     dfs序 tree数组为线段树,len为线段树长度,lazy为懒惰数组

    #include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 5e4+7;
    int n,m;
    vector<int> adj[maxn];
    int len[maxn],tree[maxn],lazy[maxn<<2],a[maxn];
    bool vis[maxn];
    int dfs(int u)
    {
        tree[u]=++m;
        int res=1;
        for(int i=0;i<adj[u].size();i++)
        {
            int v = adj[u][i];
            if(vis[v]) continue;
            vis[v] = true;
            res += dfs(v);
        }
        return len[u] = res;
    }
    
    int main()
    {
        int t,i,j;
        scanf("%d",&t);
        int ca=1;
        while(t--)
        {
            scanf("%d",&n);
            int u,v;
            for(i=1;i<=n;i++) adj[i].clear();
            memset(a,0,sizeof(a));
            memset(len,0,sizeof(len));
            for(i=1;i<n;i++)
            {
                scanf("%d%d",&u,&v);
                adj[v].push_back(u);
                a[u]++;
            }
            for(i=1;i<=n;i++)
            {
                if(!a[i])
                {
                    m = 0;
                    memset(vis,false,sizeof(vis));
                    dfs(i);
                    break;
                }
            }
        }
        return 0;
    }
    
    

     

    展开全文
  • DFS序与欧拉序的区别

    2019-10-08 21:11:55
    DFS序与欧拉序的区别 dfs序:是指将一棵树被dfs时所经过的节点顺序(不绕回原点)。 欧拉序:就是从根结点出发,按dfs的顺序在绕回原点所经过所有点的顺序。 作用 通过dfs序判断v节点的时间区间是否在u节点的时间...

    DFS序与欧拉序的区别

    dfs序:是指将一棵树被dfs时所经过的节点顺序(不绕回原点)。
    欧拉序:就是从根结点出发,按dfs的顺序在绕回原点所经过所有点的顺序。

    作用

    通过dfs序判断v节点的时间区间是否在u节点的时间区间内。
    通过欧拉序求u和v的最近公共祖先。

    用图说话

    dfs序:A-B-D-E-G-C-F-H

    欧拉序:A-B-D-D-E-G-G-E-B-C-F-H-H-F-C-A

     

    时间戳

     

    时间戳我们有两个标记,第一个是第一次访问的时候记录一下,然后是在最后一次访问时再标记一下。 

    时间戳的性质:我们可以直接通过时间戳来判断一个节点是否是另一个节点的子节点。时间戳之后,那么树的每个节点就具有了区间的性质。 

     

    DFS序

    DFS序核心代码

    const int maxn = 1e5+5;
    vector<int> g[maxn]; //存放节点
    int s[maxn], e[maxn];//s[maxn]存放“入时间戳”,e[maxn]存放“出时间戳”;
    int n,id,len;
    int dfsxu[20000];//存放dfs序
    
    void dfs(int u, int fa) {
    	s[u] = ++id;
    	dfsxu[++len]=u;
    	for(int i = 0; i < g[u].size(); ++i) {
    		int v = g[u][i];
    		if(v == fa) continue;
    		dfs(v, u);
    	}
    	e[u] = id;
    }
    

     DFS序完整代码

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    vector<int> g[maxn]; //存放节点
    int s[maxn], e[maxn];//s[maxn]存放“入时间戳”,e[maxn]存放“出时间戳”;
    int n,id,len;
    int dfsxu[20000];//存放dfs序
    
    void dfs(int u, int fa) {
    	s[u] = ++id;
    	dfsxu[++len]=u;
    	for(int i = 0; i < g[u].size(); ++i) {
    		int v = g[u][i];
    		if(v == fa) continue;
    		dfs(v, u);
    	}
    	e[u] = id;
    }
    int main() {
        memset(s,0,sizeof(s));
        memset(e,0,sizeof(e));
        memset(dfsxu,0,sizeof(dfsxu));
    	ios::sync_with_stdio(0);
    	cin >> n;
    	for(int i = 1; i < n; ++i) {
    		int u, v;
    		cin >> u >> v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	id = 0;
    	dfs(1, -1);
        cout<<"DFS序:";
        for(int i=1;s[i]!=0;i++)
        {
            cout<<dfsxu[i];
        }
        cout<<endl;
        cout<<"入时间戳:";
    	for(int i=1;s[i]!=0;i++)
        {
            cout<<s[i];
        }
        cout<<endl;
        cout<<"出时间戳:";
        for(int i=1;e[i]!=0;i++)
        {
            cout<<e[i];
        }
        cout<<endl;
    
    	return 0;
    }
    
    

    运行结果:

    通过dfs序判断v节点的时间区间是否在u节点的时间区间内

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    vector<int> g[maxn];
    int s[maxn], e[maxn];
    int n, q, id;
    void dfs(int u, int fa) {
    	s[u] = ++id;
    	for(int i = 0; i < g[u].size(); ++i) {
    		int v = g[u][i];
    		if(v == fa) continue;
    		dfs(v, u);
    	}
    	e[u] = id;
    }
    int main() {
    	ios::sync_with_stdio(0);
    	cin >> n >> q;
    	for(int i = 1; i < n; ++i) {
    		int u, v;
    		cin >> u >> v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	id = 0;
    	dfs(1, -1);
    	for(int i = 1; i <= q; ++i) {
    		int u, v;
    		cin >> u >> v;
    		if(s[u] <= s[v] && e[v] <= e[u]) {
    			cout << "YES" << endl;
    		}
    		else {
    			cout << "NO" << endl;
    		}
    	}
    	return 0;
    }
    

     

    欧拉序

    核心代码:

    vector<int> g[40010]; //存放节点
    int oulaxu[80020]; //存放欧拉序在,在欧拉序中第一次出现为“入时间戳”,第二次出现为“出时间戳”。
    int len;
    
    void dfs(int u,int fa)
    {
        oulaxu[++len]=u;
        int sz=g[u].size();
        for(int i=0; i<sz; i++)
        {
            if(g[u][i]!=fa)
                dfs(g[u][i],u);
            }
    
        oulaxu[++len]=u;
    }
    

    完整代码:

    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    vector<int> g[40010]; //存放节点
    int oulaxu[80020]; //存放欧拉序在,在欧拉序中第一次出现为“入时间戳”,第二次出现为“出时间戳”。
    int len;
    
    void dfs(int u,int fa)
    {
        oulaxu[++len]=u;
        int sz=g[u].size();
        for(int i=0; i<sz; i++)
        {
            if(g[u][i]!=fa)
                dfs(g[u][i],u);
            }
    
        oulaxu[++len]=u;
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n;
            len=0;
            memset(oulaxu,0,sizeof(oulaxu));
            scanf("%d",&n);
            for(int i=1; i<=n; i++)
            {
                g[i].clear();
            }
            for(int i=1; i<=n-1; i++)
            {
                int from,to;
                scanf("%d%d",&from,&to);
                g[from].push_back(to);
                g[to].push_back(from);
            }
            dfs(1,0);
            for(int i=1;i<=len;i++)
            {
                printf("%d ",oulaxu[i]);
            }
        }
    
    }
    
    

     运行结果

    通过欧拉序求u和v的最近公共祖先 

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    vector<int> g[maxn];
    int E[maxn*2], R[maxn], dep[maxn];
    int f[maxn*2][20];
    int n, q, cnt;
    void dfs(int u, int fa, int deps) {
    	E[++cnt] = u;
    	R[u] = cnt;
    	dep[u] = deps;
    	for(int i = 0; i < g[u].size(); ++i) {
    		int v = g[u][i];
    		if(v == fa) continue;
    		dfs(v, u, deps+1);
    		E[++cnt] = u;
    	}
    }
    void rmq_init() {
    	for(int i = 1; i <= cnt; ++i) {
    		f[i][0] = E[i];
    	}
    	for(int j = 1; (1<<j) <= cnt; ++j) {
    		for(int i = 1; i+(1<<j)-1 <= cnt; ++i) {
    			int u = f[i][j-1], v = f[i+(1<<(j-1))][j-1];
    			f[i][j] = dep[u] < dep[v] ? u : v;
    		}
    	}
    }
    int rmq(int i, int j) {
    	int k = log2(j-i+1);
    	int u = f[i][k], v = f[j-(1<<k)+1][k];
    	return dep[u] < dep[v] ? u : v;
    }
    int lca(int u, int v) {
    	return rmq(min(R[u], R[v]), max(R[u], R[v]));
    }
    int main() {
    	ios::sync_with_stdio(0);
    	cin >> n >> q;
    	for(int i = 1; i < n; ++i) {
    		int u, v;
    		cin >> u >> v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	cnt = 0;
    	dfs(1, -1, 1);
    	rmq_init();
    	for(int i = 1; i <= q; ++i) {
    		int u, v;
    		cin >> u >> v;
    		cout<<lca(u,v)<<endl;
    	}
    	return 0;
    }
    

     

    展开全文
  • DFS序——树链剖分前驱知识

    千次阅读 多人点赞 2018-09-20 21:21:19
    对于一棵树的dfs序而言,同一棵子树所对应的一定是dfs序中连续的一段。 dfs序的七个基本问题: 定义:dfs序:每个节点在dfs深度优先遍历中的进出栈的时间序列。  定义两个数组,in[x],out[x]。dfs从根结点开始...

    目录

    定义:dfs序:每个节点在dfs深度优先遍历中的进出栈的时间序列。 

     性质:dfs序可以把一棵树区间化,即可以求出每个节点的管辖区间。

    对于一棵树的dfs序而言,同一棵子树所对应的一定是dfs序中连续的一段。

    dfs序的七个基本问题:


    定义:dfs序:每个节点在dfs深度优先遍历中的进出栈的时间序列。 

    定义两个数组,in[x],out[x]。dfs从根结点开始,每个结点分别记录两个信息:in[x],out[x],in[x]为dfs进入结点x时的时间戳,out[x]为dfs离开结点x时的时间戳。

    dfs序的基本代码:

    void dfs(int x,int pre,int d){//L,R表示一个子树的范围  
        L[x]=++tot;  
        dep[x]=d;  
        for(int i=0;i<e[x].size();i++){  
            int y=e[x][i];  
            if(y==pre)continue;  
            dfs(y,x,d+1);  
        }  
        R[x]=tot;  
    }

     

    这里写图片描述 
    dfs序就是: 
    这里写图片描述

     性质:dfs序可以把一棵树区间化,即可以求出每个节点的管辖区间。

    对于一棵树的dfs序而言,同一棵子树所对应的一定是dfs序中连续的一段。

     

    这里写图片描述

     

    如下图,DFS之后,那么树的每个节点就具有了区间的性质。 
    这里写图片描述

    dfs序的七个基本问题:

    ps:deep[x]为x的深度,l[x]为dfs序中x的位置,r[x]为dfs序中x子树的结束位置

    1.点修改,子树和查询

      在dfs序中,子树处于一个连续区间中。所以这题可以转化为:点修改,区间查询。用树状数组或线段树即可。

    例:poj3321 Apple Tree

    链接:邻接表数组实现详解

    //dfs序+树状数组
    #include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    using namespace std;
    const int N = 500005;
    struct Edge{ //邻接表——数组实现 (链式前向星)
        int to,next;
    }edge[N];
    
    int head[N],tot,d[N];
    int in[N],out[N];  //in[i]:dfs第一次进入顶点i的时间戳,in[i]为dfs离开该节点的时间戳 
    bool have[N];
    int cnt;
    
    void init(){
        tot = 0;
        cnt = 0;
        memset(head,-1,sizeof(head));
        memset(d,0,sizeof(d));
    }
    
    void addEdge(int u,int v,int &k){
        edge[k].to = v;
    	edge[k].next = head[u];  //edge[k].next存储的是编号为i的边的(同样以u为起始点的)前一条边的编号 
    	head[u] = k++;  //最后一条以u为起始点的边的编号 
    }
    
    void dfs(int u){  //dfs序 
        in[u] = ++cnt;
        for(int k=head[u];k!=-1;k=edge[k].next){
            dfs(edge[k].to);
        }
        out[u] = cnt;
    }
    
    int lowbit(int x){
        return x&(-x);
    }
    
    int sum(int x){
        int res = 0;
        while(x){
        	res+=d[x];
        	x-=lowbit(x);
    	}
        return res;
    }
    
    void update(int x,int v){
    	while(x<=cnt){
    		d[x]+=v;
    		x+=lowbit(x);
    	}
    }
    
    int main()
    {
        int n,m;
        while(scanf("%d",&n)!=EOF){
            init();
            for(int i=0;i<n-1;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                addEdge(u,v,tot);
            }
            dfs(1);
            /*for(int i=1;i<=n;i++){
                printf("%d %d\n",in[i],out[i]);
            }*/
            for(int i=1;i<=n;i++){
                have[i] = 1;
                update(in[i],1);
            }
            int q;
            scanf("%d",&q);
            while(q--){
                char op;
                int x;
                scanf(" %c%d",&op,&x);  /*注意字符读入时,前面加上空格,这样可避免回车符的读入  
    									当然字符也可以以字符串的形式读入,取第一个字符,这样前面就无需加空格了*/ 
                //cout<<"op="<<op<<"x="<<endl;
                if(op=='Q'){
                    printf("%d\n",sum(out[x])-sum(in[x]-1));  //[in[x],out[x]]
                }else{
                    if(have[x]) update(in[x],-1);
                    else update(in[x],1);
                    have[x] ^= 1;   //have[x] = !have[x];
                }
            }
        }
        return 0;
    }

    2.树链修改,单点查询

      将一条树链x,y上的所有点的权值加v。这个问题可以等价为:

      1).x到根节点的链上所有节点权值加v。

      2).y到根节点的链上所有节点权值加v。

      3).lca(x,y)到根节点的链上所有节点权值和减v。

      4).fa(lca(x,y))到根节点的链上所有节点权值和减v。  

      上面四个操作可以归结为:节点x到根节点链上所有节点的权值加减v。修改节点x权值,当且仅当y是x的祖先节点时,x对y的值有贡献。

      所以节点y的权值可以转化为节点y的子树节点贡献和。从贡献和的角度想:这就是点修改,区间和查询问题。

      修改树链x,y等价于add(l[x],v),add(l[y],v),add(l[lca(x,y)],-v),add(l[fa(lca(x,y))],-v)。

      查询:get_sum(r[x])-get_sum(l[x]-1)

      用树状数组或线段树即可。

    3.树链修改,子树和查询

      树链修改部分同上一问题。下面考虑子树和查询问题:前一问是从贡献的角度想,子树和同理。

      对于节点y其到根节点的权值和,考虑其子节点x的贡献:w[x]*(deep[x]-deep[y]+1) = w[x]*(deep[x]+1)-w[x]*deep[y] 

      所以节点y的子树和为:

      

      ps:公式中的v[i]为手误,应为w[i]。

      所以用两个树状数组或线段树即可:

        第一个维护∑w[i]*(deep[i]+1):支持操作单点修改,区间和查询。(这也就是问题2)

        第二个维护∑ w[i]:支持操作单点修改,区间查询。(这其实也是问题2)

    4.单点更新,树链和查询

      树链和查询与树链修改类似,树链和(x,y)等于下面四个部分和相加:

      1).x到根节点的链上所有节点权值加。

      2).y到根节点的链上所有节点权值加。

      3).lca(x,y)到根节点的链上所有节点权值和的-1倍。

      4).fa(lca(x,y))到根节点的链上所有节点权值和的-1倍。

      所以问题转化为:查询点x到根节点的链上的所有节点权值和。

      修改节点x权值,当且仅当y是x的子孙节点时,x对y的值有贡献。

      差分前缀和,y的权值等于dfs中[1,l[y]]的区间和。

      单点修改:add(l[x],v),add(r[x]+1,-v);

    5.子树修改,单点查询

      修改节点x的子树权值,在dfs序上就是区间修改,单点权值查询就是单点查询。

      区间修改,单点查询问题:树状数组或线段树即可;

    6.子树修改,子树和查询

      题目等价与区间修改,区间查询问题。用树状数组或线段树即可。

    7.子树修改,树链查询

      树链查询同上,等价为根节点到y节点的链上所有节点和问题。

      修改节点x的子树权值,当且仅当y是x的子孙节点时(或y等于x),x对y的值有贡献。

      x对根节点到y节点的链上所有节点和的贡献为:w[x]*(deep[y]-deep[x]+1)=w[x]*deep[y]-w[x]*(1-deep[x])

      同问题三,用两个树状数组或线段树即可。

     

    参考文章:树 DFS序 详解[完全版]

    初学dfs序 

    DFS序详解

    dfs序的七个基本问题来源如下

    作者:weeping 
    出处:www.cnblogs.com/weeping/ 
    本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    展开全文
  • DFS DFS(Depth First Search),深度优先遍历,是用于遍历或者搜索树或图的算法。深度优先则指的是,其每次搜寻都会尝试往更深结点走。 DFS在搜索算法中,常常利用函数递归实现暴力枚举,而DFS在图论中,则是对图的每...

    DFS

    DFS(Depth First Search),深度优先遍历,是用于遍历或者搜索树或图的算法。深度优先则指的是,其每次搜寻都会尝试往更深结点走。

    DFS在搜索算法中,常常利用函数递归实现暴力枚举,而DFS在图论中,则是对图的每个结点的遍历。

    DFS最显著的特征在于其 递归调用自身 ,在遍历图时,对其访问的点打上访问标记,在遍历时跳过标记过的点,以确保每个点仅访问一次

    DFS大致结构如下:

    DFS(v) // v 可以是图中的一个顶点,也可以是抽象的概念,如 dp 状态等。
    	在v上打上访问标记
    	for u in v的相邻结点
    		if u没有打过标记 then
    			DFS(u)
    		end
    	end
    end
    

    实际的DFS代码需要结合操作目的添加具体功能。

    二叉树的DFS

    在数据结构中二叉树是一种重要的数据结构,其概念在此不赘述。这里用二叉树的DFS来举例DFS在图的遍历应用。

    二叉树的DFS遍历主要有三种顺序:
    前序:根左右
    中序:左根右
    后序:左右根

    具体代码:

    /*前序遍历:根左右*/
    void printPreorder(struct node* node){
        if (node == NULL){
            return;
        }
        //遍历根结点    这里对遍历到节点的操作为输出值,具体问题可以改成其它操作
        printf("%d ",node->data);  //节点操作
        //遍历左子树
        printPreorder(node->left);
        //遍历右子树
        printPreorder(node->right);
    }
    
    /*中序遍历:左根右*/
    void printInorder(struct node *node) {
        if (node == NULL){
            return;
        }
        //遍历左子树
        printInorder(node->left);
        //遍历根结点
        printf("%d ",node->data);
        //遍历右子树
        printInorder(node->right);
    }
    
    /*后序遍历:左右根*/
    void printPostorder(struct node* node)
    {
        if (node == NULL){
            return;
        }
        //遍历左子树
        printPostorder(node->left);
        //遍历右子树
        printPostorder(node->right);
        //遍历根结点
        printf("%d ", node->data);
    }
    

    DFS序

    DFS序,指的是在DFS调用过程中访问节点编号的序列。其记录了DFS遍历过程中各节点的访问顺序。这与上面二叉树的前中后序不同,前者是遍历序列,后者为遍历顺序。
    在这里插入图片描述
    该图的DFS序为: [ 1,2,3,6,4,5,7 ] 、 [ 1,5,7,4,2,6,3 ] 等。
    同一颗树的 DFS序 可以不同,这取决于其遍历顺序,但并不影响DFS序的作用。

    性质

    我们发现,因为DFS的访问特点,每一个子树都对应着DFS序列中连续的一段(一段区间)。

    	 1 , [2 , 3 , 6] , 4 , 5 , 7    子树2
    	 1 , 2 , 3 , 6 , 4 , [5 , 7 ]   子树5
    

    证明: 在dfs遍历时,当进入一个节点之后,dfs会先把当前的节点的所有子节点都遍历一遍,然后在回溯到当前节点,在这个过程中,它的所有子孙节点一定都被访问过了,而且在这之前,它的任何一个子孙节点都不可能被访问过。然后它才离开当前子树,回到父亲节点,再访问其他子树,所以同一子树的节点在dfs序中一定是连续的一段。

    这个性质使得在子树上进行的修改、查询可以转换成区间修改、区间查询。dfs序的主要作用就是将一个子树变成序列上的一个连续区间

    实现

    在DFS遍历时,顺便记录下访问顺序,例如设dfn[x]为第x个访问的节点。

    如何获得当前节点在dfs序中的范围呢?

    我们只要设一个时间 time,一开始是0,每遍历到一个新的节点就+1。那么,当前节点的访问时间范围就是当前节点的访问标号范围。设in[x]为进入当前节点时的时间,out[x]为离开当前节点时的时间,那么子树x在dfs序里所对应的范围就是in[x]~out[x]。

    但是,我们在具体操作的过程中,往往不记录dfs序,因为重要的往往是范围。注意,in[x]是第一次访问节点x的时间,in[x]≠dfn[x],而dfn[in[x]]=x。

    DFS(v) 
    	在v上打上访问标记
    	dfn[cnt] = v
    	in[v] = cnt++
    	for u in v的相邻结点
    		if u没有打过标记 then
    			DFS(u)
    		end
    	end
    	out[v] = cnt++
    end
    

    欧拉序

    欧拉序和DFS序差不多,不过欧拉序记录重复遍历到的节点。
    在这里插入图片描述
    其中一种欧拉序为:
    [ 1 , 2 , 3 , 2 , 6 , 2 , 1 , 4 , 1 , 5 , 7 , 5 , 1 ]

    在进出节点时都将其进行记录。其作用与dfs序差不多。可在求解LCA中发挥作用。

    DFS(v) 
    	在v上打上访问标记
    	O[cnt++] = v
    	for u in v的相邻结点
    		if u没有打过标记 then
    			DFS(u)
    			O[cnt++] = v
    		end
    	end
    end
    

    还有一种进入返回时加入一次:
    [ 1 , 2 , 3 , 3 , 6 , 6 , 2 , 4 , 4 , 5 , 7 , 7 , 5 , 1 ]

    DFS(v) 
    	在v上打上访问标记
    	O[cnt++] = v
    	for u in v的相邻结点
    		if u没有打过标记 then
    			DFS(u)
    		end
    	end
    	O[cnt++] = v
    end
    
    展开全文
  • DFS序

    2019-10-04 23:04:18
    DFS序就是将树形结构转化为线性结构,用dfs遍历一遍这棵树,进入到x节点有一个in时间戳,递归退出时有一个out 时间戳,x节点的两个时间戳之间遍历到的点,就是根为x的子树的所有节点,他们的dfs进入时间戳是递增的。...
  • :在求出此树的dfs序之后,子树是一段连续的区间,可以将对子树的区间操作直接化为对应序列的区间操作。 代码 : #include using namespace std; typedef long long ll; const ll MAXN=1e6+5; int n,m,root...
  • 于是我们考虑换用树状数组,仍然利用dfs序,只不过现在我们变成了用dfs序维护每个点到根这些链被直接会被增加多少,也可以看做是自底向上的差分,我们记点 k k k 的这个值为 v [ k ] v[k] v [ k ] . 然后我们维护...
  • dfs序+线段树入门题

    2019-10-06 21:19:59
    题解:简单讲一下dfs序,其实就是你搜索树的先后顺序,然后这题你只要考虑一段区间dfs序最大和最小的节点会对lca产生影响,这很好理解,那么我们只需要用线段树维护一下这些点的dfs序,求个最大次大,最小次小,就...
  • DFS序 + 线段树

    2020-04-22 22:38:06
    简单来说,就是利用dfs的连续性,把一棵树进行重新分配标号,最后把一棵树转化为一个区间用线段树或者树状数组维护的思维。 例题 核心部分: void dfs(int x,int f){ in[x] = ++tim;//tim相当一个时间戳和Tarjan...
  • dfs序与树链剖分

    2021-08-24 20:49:13
    dfs序 dfs序是对于一棵树而言,我们dfs的顺序。 主要目的是用于对一棵树上的结点形成一个数组,可以用于建线段树等操作。 在dfs序中,每个节点只出现一次(欧拉序每个节点出现两次)。 比如者一棵树的dfs序为 ...
  • dfs序+树状数组

    2020-01-19 10:20:38
    //先求出dfs序将其线性化,再利用树状数组维护区间和及单点修改; const int N = 1e5 + 55 ; //单点修改时只修改ru[x],查询时查询ru[x]~out[x]区间范围的值; int in [ N ] , out [ N ] , tr [ N ] = { 0 }...
  • dfs序(基础讲解)

    2020-08-27 16:08:13
    dfs序简介 dfs序一般用于树状结构中,如图: 图中红色序号为每个点对应的dfs序序号,黑色序号为每个点默认的序号,我称之为节点序序号(下文同) 可见,dfs序如其名,dfs序序号是按照dfs顺序标记的,所以说给每个...
  • DFS序 前置的几道题 线段树DFS序 1 单点更新 区间查询 https://blog.csdn.net/qq_40831340/article/details/84501232 线段树DFS序 2 区间子树更新 单点查 ...以上都是关于统计 跟改子树的 欧拉序 这里我们可以处理出 .....
  • DFS 3,树上差分1 Time Limit: 2000 MS Memory Limit: 131072 K Problem Description 这是一道模板题。 给一棵有根树,这棵树由编号为1…N的N个结点组成。根结点的编号为 R。每个结点都有一个权值,结点i的...
  • DFS序详解

    千次阅读 2018-08-21 16:50:36
    树通常有多种类型,但其终归是非线性结构,操作起来有时总是那么费时。 例如:POJ 3321 给你一棵树,树上每个节点都有1个苹果,然后你对一个节点操作,如果有苹果就拿走,没苹果就放上,然后询问你以x为根的子树...
  • dfs序+线性dp 树

    2020-05-09 23:34:16
    题目描述 shy有一颗树,树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的,当且仅当对于所有相同颜色的点对(x,y),x到y的路径上的所有点的颜色都要与...转化为dfs序,就是一道线性dp,dp[i][j]表示前 i
  • DFS序 详解[完全版]

    万次阅读 多人点赞 2017-11-02 15:06:43
    dfs序是指:每个节点在dfs深度优先遍历中的进出栈的时间序列。 所以它有什么用呢 我们知道,树是一种非线性的数据结构,它的一些数据调用肯定是没有线性结构来得方便的。所以这个时候,dfs站了出来。基于dfs...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,607
精华内容 16,642
关键字:

dfs序