精华内容
下载资源
问答
  • DFS序列、割点与破圈法

    千次阅读 2018-05-16 20:58:27
    DFS序、割点与破圈法概述DFS序列是图论中的基础,因为DFS序的变形与延伸算法占有图论的基础。割点与破圈则是DFS延伸的算法或概念。DFS现在一直被理解为深度优先搜索这个算法架构,其实并不是啊,在多本参考文献中DFS...

    DFS序、割点与破圈法

    概述

    DFS序列是图论中的基础,因为DFS序的变形与延伸算法占有图论的基础。割点与破圈则是DFS延伸的算法或概念。

    DFS现在一直被理解为深度优先搜索这个算法架构,其实并不是啊,在多本参考文献中DFS一直以DFS序的形式出现,而所谓的深搜只是浅层次的含义。

    什么是DFS序(DFS)?
    dfs序,顾名思义,就是dfs深度优先搜索经过的点的序列;所以dfs序具有这几个性质:知道哪个点连接自己、知道是第几个遍历的点等

    U.color存储着当前状态

    GRAY为正在访问,WHITE为未访问,BLACK为被访问过。

    U.π代表了连接它的父亲节点。

    U.d表示了第一时间戳,U.f表示了第二时间戳。

    我们不妨设图Gπ=V,Eπ),其中

    Eπ={v.π,v):vVv.π≠NIL}

    Eπ为树边,Gπ的前驱子图为Gπ=VπEπ))

    每个结点的初始颜色都是白色,在结点被访问时为灰色,其邻接链表被扫描后变成黑色。

    第二时间戳v.f记录了搜索完成对v的邻接链表扫描的时间(被标BLACK时)

    而第一时间戳v.d记录了v被发现时的时间(被标GRAY时)

    显然对于每一个结点u

    u.d<u.f

    而对于输入图G既可以是有向图,也可以是无向图。

    DFS序的过程与DFS

    上伪代码过程(参考见算法导论P350

    DFSG

      For each vertex u G.V

         u.color=WHITE

         u.π=NIL

      Time=0

      For each vertex uG.V

    If u.color==WHITE

       DFS_VISIT(G,u)

    DFS_VISIT(G,u)

      Time++

      u.d=time;

      u.color=GRAY

      For each vADJ[u]

         If v.color==WHITE

            v.π=u

            DFS_VISIT(G,v)

      u.color=BLACK

    Time++

    u.f=time

    其实过程的描述就是将G中的u点深搜,只要u未访问就深搜u,更新出入时 间戳以及u临边v的过程。

    DFS

    先来看一组样例(详见算法导论P354

     

    问:求解所点的遍历后的状态。

    (这实在太简单啦!)

    q[.d=1 .π=NIL .f=16 .color=BLACK]

    s[.d=2 .π=q  .f=7 .color=BLACK]

    v[.d=3 .π=s .f=6 .color=BLACK]

    w[.d=4 .π=v .f=5 .color=BLACK]

    t[.d=8 .π=q .f=15 .color=BLACK]

    x[.d=9 .π=t .f=12 .color=BLACK]

    z[.d=10 .π=x .f=11 .color=BLACK]

    y[.d=13 .π=t .f=14 .color=BLACK]

    r[.d=17 .π=NIL .f=20 .color=BLACK]

    u[.d=18 .π=r .f=19 .color=BLACK]

    是不是看上去比较混乱?

    为了跟好精确的标出(理解)DFS序,有一种使用树形结构的存储方式(我们暂且可以叫它DFS树),它将结点编号作为树结点,将出入时间戳标成区间形式([d,f]

    ,如下图。

     

     

      我们发现了什么???

      任意两点间的时间戳区间有三种情况:

    1. u包含v,则uv的祖先

    2. v包含u,则vu的祖先

    3. uv不是包含关系,则uv不在同一条树枝上。

    同时,在DFS上的都是合法的树边,不存在有环的边。

    也就是说,只要我们求出了DFS树,我们就可以求出DFS的合法边以及任意两点的关系了。

    代码(DFS序):

    Void DFS(int u)

    {

        For (int i=1;i<=G.len;u++)

    {

           U[i].color=WHITE

           U[i].path=0;

        }

        Time=0;

        For (int i=1;i<=G.len;i++)

    If U[i].color==WHITE

          DFS_VISIT(i);

     }

    Void DFS_VISIT(int u_xb)

    {

      Time++;

      U[u_xd].d=Time;

      U[u_xd].color=GRAY;

      For (int i=1;i<=ADJsum;i++)

         If ADJ[i].color==WHITE

    {

            U[ADJ[i].path]=i;

            DFS_VISIT(ADJ[i]);

         }

        U[u_xd].color=BLACK;

    Time++;

    U[u_xd].f=Time;

    }

     

    割点

    割点的含义就是一个图中除去某些点图就不连通,将这些点称之为割点。也就说割点是一张图的开关。

    求解割点

    其实求解割点十分简单,我们不难发现,直接一遍DFS,求解DFS树,在DFS树中遇到树边继续做,剩下的边则不用做(称之为回边),直接跳过。这种算法可以过题。

    当然,求解割点也可以用Tarjan算法。

    Tarjan算法与求解割点

    介绍一下Tarjan算法

    它是由美国科学家Tarjan发明的算法,用于解强连通分量的线性时间而诞生的算法。同时你需要知道——强连通分量到底是啥?

    涨知识:强连通分量即在有向图中存在一个子图,子图中每两个点均满足强连通,我们把这个子图叫做强联通分量。(不需要我再解释强联通吧)

    Tarjan算法就是使用DFS来实现将强连通分量在一棵搜索树上的子树。所谓的图,其实就是这棵树。

    我们先声明一下,Tarjan的每一个结点都有两个通用代号:

    一个是DFN存储时间戳,另一个叫LOW存储最小的子树的根His fathers time它父亲的时间戳

    我们可以使用堆栈来存储这个结构,只要每次new一个点就进栈,有出度就出栈,直到找到最后一层。

    那么,如何使用Tarjan求解割点呢?

    其实也很简单,我们分两种情况

    对于根节点:只要判断不是陈独秀(有两个及以上的树枝)就OK(是割点)。

    对于非根节点:

    设当前边为(u,v)

    Tarjan(int u,v)

    {

    Low[u]=Dfn[u]

    if color[v]==WHITE

    {

         DFS(v);

           Low[u]=min(Low[u],Low[v])

    }

    Else(默认u非v祖)

    Low[u]=min(Low[u],Dfn[v])

    }

    为什么上代码?

    道理很简单,只要Low[u]>=Dfn[u],u一定是割点。

    破圈法求解MST

    对于最小生成树(MST)大家一定不陌生,由PrimKruskal俩大佬发明的算法被我们今天所广泛利用,已经少有人知破圈法求MST(有人会打我),难道是因为国产算法不热?

    破圈法由我国科学家管梅谷提出来的,在国际图论界有极高评价。

    破圈法是一个动态的算法,相对于Primkrukal更有发展空间,对于pprim)和kkruskal)都是增加点或边(避圈),而破圈法提出了删边的理论:见圈破圈。

    破圈法的思想步骤有三步:

    1.  找到回路。

    2.  删除一条除割边以外权值最大的边。

    3. 重复以上操作,直到没有环为止。

    破圈法有神马作用呢?

    当然有作用,可以解动态增删边的问题,时间复杂度也不大。

    可惜这种问题对于DFS序是无法解决的,为什么?

    DFS序是定死的,再加一条边或删去。。。

    重新做一遍吧。

    当样例再加两个0

    BOOM

    (资料不多啊,所以没有代码,敬请谅解)

    参考文献

    算法导论原书第3版(DFS深度优先搜索)

    全网最!详!细!Tarjan算法讲解。

    破圈法-百度百科。

    割点-百度百科。

    转载问题

    欢迎转载!转载须标明出处与作者。

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 题解:直接从树的角度解决很难,因为不属于一种常用的树形数据结构,考虑dfs的序列的思想,可以将此问题转化为,求出根右左的dfs序列,然后对这个序列求最长上身子序列(LIS)即可解决,复杂度O(nlogn)。 需要注意的...

    原题链接:https://ac.nowcoder.com/acm/contest/368/B
    在这里插入图片描述
    题解:直接从树的角度解决很难,因为不属于一种常用的树形数据结构,考虑dfs的序列的思想,可以将此问题转化为,求出根右左的dfs序列,然后对这个序列求最长上身子序列(LIS)即可解决,复杂度O(nlogn)。
    需要注意的这个题,用Java写会再dfs的时候,会出现JVM栈溢出,所以只能通过90%,需要扩栈,C++不会出现这个问题。

    import java.util.*;
    
    public class Main implements Runnable{
    
        private final int mod = 1000000007, max = 100005;
        private int [] w = new int[max], dfsSqu = new int[max], l = new int[max], r = new int[max], dp = new int[max];
        private int cnt = 0;
    
        public static void main(String[] args) {
            new Thread(null, new Main(),"Thread-1", 1024*1024*10).start();
        }
    
        @Override
        public void run() {
            try{
                solve();
            }catch (Exception e){
                e.printStackTrace();
            }
        }
    
        private void solve(){
            Scanner cin = new Scanner(System.in);
            int n = cin.nextInt();
            for(int i=1; i<=n; i++){
                w[i] = cin.nextInt();
            }
            for(int i=1; i<=n; i++){
                l[i] = cin.nextInt();
                r[i] = cin.nextInt();
            }
    
            dfs(1);//获取dfs序列
    
            //LIS
            dp[0] = dfsSqu[0];
            int len = 1;
            for(int i=1; i<cnt; i++){
                if(dfsSqu[i] > dp[len-1]){
                    dp[len++] = dfsSqu[i];
                }else{
                    dp[lower_bound(0, len-1, dfsSqu[i])] = dfsSqu[i];
                }
            }
            System.out.println(len);
        }
    
        private void dfs(int root){
            if(root == 0){
                return;
            }
            dfsSqu[cnt++] = w[root];
            dfs(r[root]);
            dfs(l[root]);
        }
    
        private int lower_bound(int lower, int higher, int key) {
            while(lower < higher){
                int mid = ((higher - lower) >> 1) + lower;
                if(key <= dp[mid]){
                    higher = mid;
                }else{
                    lower = mid+1;
                }
            }
            return lower;
        }
    }
    
    
    
    
    

    dfs序列的思想很值得学习,LIS也是经典dp之一,另外Java扩栈也是值得学习的经验。

    展开全文
  • Snacks HDU 5692 dfs序列+线段树 题意 百度科技园内有n个零食机,零食机之间通过n−1条路相互连通。每个零食机都有一个值v,表示为小度熊提供零食的价值。 由于零食被频繁的消耗和补充,零食机的价值v会时常发生...

    Snacks HDU 5692 dfs序列+线段树

    题意

    百度科技园内有n个零食机,零食机之间通过n−1条路相互连通。每个零食机都有一个值v,表示为小度熊提供零食的价值。

    由于零食被频繁的消耗和补充,零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发,并且每个零食机至多经过一次。另外,小度熊会对某个零食机的零食有所偏爱,要求路线上必须有那个零食机。

    为小度熊规划一个路线,使得路线上的价值总和最大

    输入输出:

    输入数据第一行是一个整数T(T≤10),表示有T组测试数据。

    对于每组数据,包含两个整数n,m(1≤n,m≤100000),表示有n个零食机,m次操作。

    接下来n−1行,每行两个整数x和y(0≤x,y<n),表示编号为x的零食机与编号为y的零食机相连。

    接下来一行由n个数组成,表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。

    接下来m行,有两种操作:0 x y,表示编号为x的零食机的价值变为y;1 x,表示询问从编号为0的零食机出发,必须经过编号为x零食机的路线中,价值总和的最大值。

    本题可能栈溢出,辛苦同学们提交语言选择c++,并在代码的第一行加上:

    #pragma comment(linker, "/STACK:1024000000,1024000000") 

    题解思路

    dfs序列的题,这是第一道,当然不出意外,我不会做。但是我找到一篇写的非常好的博客,详细解释了这个题。点我链接

    思路就是用dfs序列,将树“拍”成一维的一串,这样就可以用线段树或者树状数组进行接下来的操作了。

    至于为什么要转化为一维的,因为简单啊,并且用来处理一维数据的方法也很多。

    代码实现

    两种形似,第一个是数组形式的线段树,有注释。第二种是使用结构体线段树,和第一种基本一样。

    #pragma comment(linker, "/STACK:1024000000,1024000000")
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    vector <int> a[100001];
    int n,m,now = 0,b[100001],xulie[100005],e[100005];
    long long v[100005],dis[100005] ={0},maxsum[100005*4],lazy_tag[100005*4] = {0};
    
    void dfs(int x,int pre)//深搜找dfs序
    {
        b[x] = ++now;//这是这个节点的开始位置
        xulie[now] = x;//把这个序号的节点加入到序列中
        int len = a[x].size();//这是x节点的出度
        for(int i = 0;i <= len-1;i++)//vector是从0开始计数的
        {
            int y = a[x][i];//x的一个出度。
            if (y!=pre)//如果没有往回走
            {
                dis[y] = dis[x]+v[y];//更新y节点它到0点的价值和
                dfs(y,x);//继续dfs
            }
        }
        e[x] = now;//这是节点的结束位置。b[x]..e[x]里面存的都是x的子树节点。
    }
    
    long long max(long long a,long long b)
    {
        return a > b?a:b;
    }
    
    void push_up(int rt)
    {
        maxsum[rt] = max(maxsum[rt<<1],maxsum[rt<<1|1]);//只要左右区间的最值取max就可以了。
    }
    
    void build(int l,int r,int rt)
    {
        lazy_tag[rt] = maxsum[rt] = 0;//初始化懒惰标记和区间最值。
        if (l == r)//如果左右指针相同
        {
            maxsum[rt] = dis[xulie[l]];//这个区间的最大值就是本身
            return;//注意不要写成maxsum[rt] = dis[l],l是dfs序,xulie[l]才是这个dfs序所代表的点
        }
        int m = (l+r)>>1;//取得中点
        build(l,m,rt<<1);//左递归建树
        build(m+1,r,rt<<1|1);//右递归建树
        push_up(rt);//根据儿子更新当前区间的最值。
    }
    
    void push_down(int rt)
    {
        if (lazy_tag[rt]!=0) //如果懒惰标记标记的值不为0
        {
            maxsum[rt<<1]+=lazy_tag[rt];//更新儿子节点们的区间最值(记住是同等更新就好)
            maxsum[rt<<1|1] += lazy_tag[rt];
            lazy_tag[rt<<1]+=lazy_tag[rt];//更新儿子节点们的懒惰标记。
            lazy_tag[rt<<1|1]+=lazy_tag[rt];
            lazy_tag[rt]=0;//把当前节点的懒惰标记置为0;
        }
    }
    
    void updata(int l,int r,int num,int begin,int end,int rt) //所要修改的区间为l,r,当前节点rt的区间
    {//为begin,end,然后要递增的值为num
        if (l <= begin && end <= r) //如果当前节点所在的区间被所要修改的区间覆盖
        {
            maxsum[rt]+=num;//递增这个区间的最大值(因为是同等递增,所以直接把最大值+递增值就可以);
            lazy_tag[rt] +=num;//标一个懒惰标记。
            return;
        }
        push_down(rt);//处理懒惰标记。
        int m = (begin+end)>>1;//取中点
        if (l <= m)//往左递增值
            updata(l,r,num,begin,m,rt<<1);
        if (m < r)//往右递增值。
            updata(l,r,num,m+1,end,rt<<1|1);
        push_up(rt);//根据儿子节点更新当前节点。
    }
    
    long long query(int l,int r,int begin,int end,int rt)//要找的区间为l,r,当前节点rt所代表的区间为begin,end;
    {
        if (l <= begin && end <= r)//如果当前节点所在的区间完全在要找的区间内
            return maxsum[rt];//就直接返回这个区间的最大值
        long long temp_ans= -10000000000;//这是用于取左右区间最大值的较大值。
        int m = (begin+end)>>1;
        push_down(rt);//先处理懒惰标记!!!!!!!!!!!!
        if (l <= m)//如果左区间和所找的区间有交集,就看看左区间是否更大
            temp_ans = max(temp_ans,query(l,r,begin,m,rt<<1));
        if (m < r)//右区间同理
            temp_ans = max(temp_ans,query(l,r,m+1,end,rt<<1|1));
        return temp_ans;//返回左右区间的较大值即可。
    }
    
    int main()
    {
        //freopen("rush.txt","r",stdin);
        int t;
        scanf("%d",&t);//输入数据的组数
        for (int ii = 1;ii <= t;ii++)//不要写成while (t--)。。。这样写你要怎么输出呢。。。
        {
            now = 0;//dfs序号从0再重新开始
            for (int i = 0;i <= 100000;i++)//初始化某个点的出度信息。
                a[i].clear();
            printf("Case #%d:\n",ii);//输出这是第几组数据
            scanf("%d%d",&n,&m);//输入点和边的信息。
            for (int i = 1;i <= n-1;i++)//输入n-1条边(就是树了!)
            {
                int x,y;
                scanf("%d%d",&x,&y);//输入起点和终点
                a[x].push_back(y);//建一条双向边。
                a[y].push_back(x);
            }
            for (int i = 0;i <= n-1;i++)//输入点的初始价值。
                scanf("%lld",&v[i]);
            dis[0] = v[0];//从0到0就是0点的价值。
            dfs(0,-1);//进行dfs,获取0到所有点的价值和。
            build(1,n,1);//建树。
            for (int i = 1;i <= m;i++)//输入m个操作。
            {
                int op,x,y;
                scanf("%d",&op);//读取操作
                if (op == 0)//如果要改变某个值
                {
                    scanf("%d%d",&x,&y);
                    updata(b[x],e[x],y-v[x],1,n,1);//把替换操作改为递增操作。要进行修改的区间就是
                    v[x] = y;//x的子树所在的区间。
                    //v[x]下次可能还会用到所以要修改一下。
                }
                else
                {
                    scanf("%d",&x);//读入x,表示要经过x(然后从x和x的子树节点里面选一个节点到那里)
                    cout << query(b[x],e[x],1,n,1) << endl;//在x的子树节点所在区间内找最大价值
                }
            }
        }
        return 0;
    }
    #pragma comment(linker, "/STACK:1024000000,1024000000") 
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+7;
    int in[maxn], out[maxn], xulie[maxn];
    ll dis[maxn], v[maxn];
    vector<int> g[maxn];
    struct node{
        int l, r;
        ll maxx, lazy;
    }t[maxn<<2];
    int n, m, now;
    void init()
    {
        now=0;
        for(int i=0; i<=n; i++)
        {
            g[i].clear();
        }
    }
    void dfs(int rt, int fa)
    {
        in[rt]=++now;
        xulie[now]=rt;
        int len=g[rt].size();
        for(int i=0; i<len; i++)
        {
            int y=g[rt][i];
            if(y==fa) continue;
            dis[y]=dis[rt]+v[y];
            dfs(y, rt);
        }
        out[rt]=now;
    }
    void pushup(int rt)
    {
        t[rt].maxx=max(t[rt<<1].maxx, t[rt<<1|1].maxx);
    }
    void build(int rt, int l, int r)
    {
        t[rt].l=l;
        t[rt].r=r;
        t[rt].lazy=0;
        if(l==r)
        {
            t[rt].maxx=dis[xulie[l]];
            return ;
        }
        int mid=(l+r)>>1;
        build(rt<<1, l, mid);
        build(rt<<1|1, mid+1, r);
        pushup(rt);
    } 
    void down(int rt)
    {
        if(t[rt].lazy!=0)
        {
            t[rt<<1].maxx+=t[rt].lazy;
            t[rt<<1].lazy+=t[rt].lazy;
            
            t[rt<<1|1].maxx+=t[rt].lazy;
            t[rt<<1|1].lazy+=t[rt].lazy;
            
            t[rt].lazy=0;
        }
    }
    void update(int rt, int l, int r, int y)
    {
        if(l<=t[rt].l && t[rt].r <=r)
        {
            t[rt].maxx+=y;
            t[rt].lazy+=y;
            return ;
        }
        down(rt);
        int mid=(t[rt].l+t[rt].r)>>1;
        if(l<=mid) update(rt<<1, l, r, y);
        if(r>mid) update(rt<<1|1, l, r, y);
        pushup(rt);
    }
    ll query(int rt, int l, int r)
    {
        if(l<= t[rt].l && t[rt].r<=r)
        {
            return t[rt].maxx;
        }
        ll ans=-1e18;
        int mid=(t[rt].l+t[rt].r)>>1;
        down(rt);
        if(l<=mid) ans=max(ans, query(rt<<1, l, r));
        if(r>mid) ans=max(ans, query(rt<<1|1, l, r));
        return ans;
    }
    int main()
    {
        int t;
        scanf("%d", &t);
        for(int ca=1; ca<=t; ca++)
        {
            scanf("%d%d", &n, &m);
            init();
            printf("Case #%d:\n", ca);
            for(int i=1; i<n; i++)
            {
                int x, y;
                scanf("%d%d", &x, &y);
                g[x].push_back(y);
                g[y].push_back(x);
            }
            for(int i=0; i<=n-1; i++)
            {
                scanf("%lld", &v[i]);
            }
            dis[0]=v[0];
            dfs(0, -1);
            build(1, 1, n);
            for(int i=1; i<=m; i++)
            {
                int op, x, y;
                scanf("%d", &op);
                if(op==0)
                {
                    scanf("%d%d", &x, &y);
                    update(1,in[x], out[x], y-v[x]);
                    v[x]=y;
                }
                else 
                {
                    scanf("%d", &x);
                    printf("%lld\n", query(1, in[x], out[x]));
                }
            }
        }
        return 0;
    } 

    转载于:https://www.cnblogs.com/alking1001/p/11383492.html

    展开全文
  • 思路:一道线段树+DFS序列的好题,考察很全面,题解很多不赘述了,训练了DFS序列以及把边转化为点的思想。(用cin没关同步会TLE) 1 /***********************************************************************...

    2014-10-03 02:22:29

    思路:一道线段树+DFS序列的好题,考察很全面,题解很多不赘述了,训练了DFS序列以及把边转化为点的思想。(用cin没关同步会TLE)

      1 /*************************************************************************
      2     > File Name: 5039.cpp
      3     > Author: Nature
      4     > Mail: 564374850@qq.com
      5     > Created Time: Thu 02 Oct 2014 10:50:41 PM CST
      6 ************************************************************************/
      7 
      8 #include <cstdio>
      9 #include <cstring>
     10 #include <cstdlib>
     11 #include <cmath>
     12 #include <vector>
     13 #include <queue>
     14 #include <string>
     15 #include <map>
     16 #include <iostream>
     17 #include <algorithm>
     18 using namespace std;
     19 #define lp (p << 1)
     20 #define rp (p << 1|1)
     21 #define getmid(l,r) (l + (r - l) / 2)
     22 typedef long long ll;
     23 const int INF = 1 << 30;
     24 const int maxn = 60010;
     25 
     26 int T,N,M;
     27 int sta[maxn],t1[maxn],t2[maxn],tot,stval[maxn];
     28 int first[maxn],next[maxn],ver[maxn],ecnt;
     29 map<string,int> mp;
     30 string name,s1,s2;
     31 pair<int,int> e[maxn];
     32 
     33 struct node{
     34     int sum,cover;
     35 }t[maxn << 2];
     36 
     37 void Add(int u,int v,int x){
     38     next[++ecnt] = first[u];
     39     first[u] = ecnt;
     40     ver[ecnt] = v;
     41     sta[ecnt] = x;
     42 }
     43 
     44 void Dfs(int p,int pre,int val){
     45     t1[p] = ++tot;
     46     stval[tot] = val;
     47     for(int i = first[p]; i; i = next[i])
     48         if(ver[i] != pre) Dfs(ver[i],p,val ^ sta[i]);
     49     t2[p] = tot;
     50 }
     51 
     52 void Push_up(int p){
     53     t[p].sum = t[lp].sum + t[rp].sum;
     54 }
     55 
     56 void Build_tree(int p,int l,int r){
     57     t[p].cover = 0;
     58     if(l == r){
     59         t[p].sum = stval[l];
     60         return;
     61     }
     62     int mid = getmid(l,r);
     63     Build_tree(lp,l,mid);
     64     Build_tree(rp,mid + 1,r);
     65     Push_up(p);
     66 }
     67 
     68 void Push_down(int p,int l,int mid,int r){
     69     if(t[p].cover){
     70         t[lp].cover ^= 1;
     71         t[lp].sum = mid - l + 1 - t[lp].sum;
     72         t[rp].cover ^= 1;
     73         t[rp].sum = r - mid - t[rp].sum;
     74         t[p].cover = 0;
     75     }
     76 }
     77 
     78 void Update_tree(int a,int b,int p,int l,int r){
     79     if(a <= l && r <= b){
     80         t[p].cover ^= 1;
     81         t[p].sum = r - l + 1 - t[p].sum;
     82         return;
     83     }
     84     int mid = getmid(l,r);
     85     Push_down(p,l,mid,r);
     86     if(a <= mid) Update_tree(a,b,lp,l,mid);
     87     if(b > mid) Update_tree(a,b,rp,mid + 1,r);
     88     Push_up(p);
     89 }
     90 
     91 void Init(){
     92     memset(first,0,sizeof(first));
     93     ecnt = tot = 0;
     94 }
     95 
     96 int main(){
     97     ios::sync_with_stdio(false);
     98     char s[5];
     99     int x,id1,id2;
    100     cin >> T;
    101     for(int Case = 1; Case <= T; ++Case){
    102         Init();
    103         cin >> N;
    104         for(int i = 1; i <= N; ++i){
    105             cin >> name;
    106             mp[name] = i;
    107         }
    108         for(int i = 1; i < N; ++i){
    109             cin >> s1 >> s2 >> x;
    110             id1 = mp[s1];
    111             id2 = mp[s2];
    112             Add(id1,id2,x);
    113             Add(id2,id1,x);
    114             e[i] = make_pair(id1,id2);
    115         }
    116         Dfs(1,0,0);
    117         Build_tree(1,1,N);
    118         printf("Case #%d:\n",Case);
    119         cin >> M;
    120         for(int i = 1; i <= M; ++i){
    121             cin >> s;
    122             if(s[0] == 'Q'){
    123                 int tmp = t[1].sum;
    124                 printf("%d\n",tmp * (N - tmp) * 2);
    125             }
    126             else{
    127                 cin >> x;
    128                 int u = e[x].first;
    129                 int v = e[x].second;
    130                 if(t1[u] < t1[v]) u = v;
    131                 Update_tree(t1[u],t2[u],1,1,N);
    132             }
    133         }
    134     }
    135     return 0;
    136 }

     

    转载于:https://www.cnblogs.com/naturepengchen/articles/4004687.html

    展开全文
  • 0 1 4 2 5 3 和 0 2 5 1 4 3 和 3 2 5 1 4 0 都是合法的DFS序列,但0 2 3 1 4 5则不是合法的DFS序列。 输入格式: 第一行给出顶点数 M 和边数 N,以空格分隔;顶点标号从 0 到 M−1。其中 M 不超过 100。 之后 N 行,...
  • DFS序列+线段树
  • 解题思路:用dfs求出整棵树的dfs序列,这样以u为根节点的子树就转化到相对应的区间上了。由于是区间不修改查询问题,这个时候就可以用莫队算法了。 #pragma comment(linker, "/STACK:16777216") #include #include...
  • 并查集 #include<stdio.h> int stt[10005]; void sset(int x) { for(int i=1;i<=x;i++) stt[i]=i; } int ffind(int x) { if(x==stt[x]) return x;... else return stt[x]=ffind(s...
  • 首先遍历得到dfs序列,离线后按照C排序再从小到大插入和查询,每一次相当于单点修改和链上查询,然后用树状数组来维护区间修改单点查询就好了。(根本不需要用什么树链剖分)。O(NlogN)+常数小,成功用小号刷到rank2...
  • dfs序列 的lis

    2016-11-02 16:27:20
    dfs(node[x].ls);cnt++; lis[cnt]=a[x]; dfs(node[x].rs); } int Ma[maxn*4]; int Max(int node,int tl,int tr) { if(tl>=L&&R>=tr) { return Ma[node];} int mid=(tl+tr)>>1;int cmax=0; if(L) cmax=max(cmax,...
  • hihocoder#1069 : 最近公共祖先·三(DFS序列+线段树)上上回说到,小Hi和小Ho使用了Tarjan算法来优化了他们的“最近公共祖先”网站,但是很快这样一个离线算法就出现了问题:如果只有一个人提出了询问,那么小Hi和...
  • 思路:我们从dfs序入手。 dfs相邻的两个节点AB。可能是父子节点,可能不是父子节点。 我们主要不与bfs序,矛盾就可以了。 满足下面情况的任何一种情那么就可以说AB是父子关系。 1、bfs序A的位置+1<bfs序B的位置 2...
  • Codeforces-877E:Danil and a Part-time Job(DFS序列+线段树)Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher. Danil works...
  • 不过由于本题不强制在线,所以用dfs序列会简单得多。代码长度差不多,但线段树明显快得多(当然像我这种写得这么烂的除外)。  首先,如果用线段树维护,那么我们就要求操作时的区间是连续的,这样就可以用线段树的...
  • 大体题意: 给你一颗树,ri 为以当前结点为根的最小子树上的权值(单点),每个点有固定的权值vi,每个点的权值都不一样,每次你必须优先访问ri最小的,然后删掉,然后重新计算ri,求这个...直接给这棵树 进行dfs序列
  • 题目(阿里笔试题):以下是一个有向图,我们从节点B开始进行深度优先遍历(DFS),那么以下5个序列中,所有正确的DFS序列是__。 解析:深度优先遍历是指优先探索完一条通路后才返回倒数第二个节点继续探索另一条...
  • 题目链接:http://codeforces.com/problemset/problem/782/E #include <bits/stdc++.h> using namespace std; vector<int> e[200005], f; ...void dfs(int u){ vis[u]=1; f.pus...
  • Description 给出一棵树,要求资磁一下三个操作 1. 换根为x 2. 将x的子树内所有点权加上y 3. 记x,y的lca为z,求z所在子树内...对于操作2我们可以根据x和root的相对关系判断是dfs序上的连续一段还是它的补集...
  • hdu 4366 线段树+dfs序列

    2015-12-25 19:44:09
    void dfs(int x) { in[x] = time++; for(int i = head[x]; i!=-1; i=e[i].next) { dfs(e[i].v); } out[x] = time++; } void init() { int fa; ed = time = 0; MS(head,-1);MS(ans,-1);MS(maxv,-1); mp....
  • } void DFS(int u, int fa) { dfn[u] = ++tim; siz[u] = 1; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; if (v == fa) continue; DFS(v, u); siz[u] += siz[v]; } } void update(int x, int...
  • ACM题集:... 树的DFS序,时间戳 /*树的DFS序*/ #include&lt;bits/stdc++.h&gt; #define ll long long #define fo(i,j,n) for(register int i=j; i&lt;=n; ++i) us...
  • 树链刨分把DFS序搞出来,为之后求LCA做准备,对五个点根据DFS序排序,找到DFS序最小和DFS序最大的点的LCA(因为在一个颗子树中的DFS序是连续的,所以这样就可以包含住所有的点),之后把剩余三个点并到这条链上,并...
  • i = next[i]) dfs(to[i]); last[x] = tot; } void pushup(int x) { int l = x , r = x | 1; if(mx[l] > mx[r]) mx[x] = mx[l] , mp[x] = mp[l]; else mx[x] = mx[r] , mp[x] = mp[r]; } void pushdown(int x) {...
  • 比如有下面这个图,从1开始dfs,则dfs序列可以是1->2->4->5->3->5->4->2->1,假如k=3,则第一个人走1->2->4->5,第二人走3->5->4->2,剩下的人走1即可     #include #include #include #include ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,615
精华内容 1,446
关键字:

dfs序列