dfs序线段树

dfs序+线段树，啥？如果在一棵树上，需要你修改一些节点和查询一些节点，如果直接dfs搜的话肯定超时，那用线段树？树结构不是区间啊，怎么用？用dfs序将树结构转化为一个区间，就能用线段树进行维护了。

dfs序是指：每个节点在dfs深度优先遍历中的进出栈的时间序列，记录每个点进栈和出栈的时间点，会发现每个点在栈中出现两次

比如下面这个图的dfs序：

（转载来的图片，太懒不想画）

那么这样转化后我们就可以在上面进行线段树了。对于进栈时间点，我们记录为left[ u ]，出栈时间点为right[ u ] 。对于这个区间，我们将每个节点标记为 1~len（dfs序长度）

以这个为区间1~len建线段树，然后那棵树就没用了！，没用了！对于修改一个节点x，就是修改left[x]（但你的len是等于n的，或者你如果建的是两个节点都算的，你需要update左右编号），对于查询一个区间，就是查询left[x]~right[x]，实际上就是线段树。

但是我在刚理解时候总会受原来那颗树的影响，实际上，可以这样理解，比如在这个dfs序中你要修改树节点1（原本的值都是1）

------------------------------>

附上一个例题

POJ 3321

There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.

The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won't grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.

The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?

Input

The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
"C x" which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
"Q x" which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning

Output

For every inquiry, output the correspond answer per line.

Sample Input

Sample Output

3

2

 var

 left,right,next,head,a,value:array[..]of longint;

 n,m,k,x,y,e,tot,s:longint;

 i:longint;

 ch:char;

 procedure add(x,y:int64);

  begin

   inc(e);a[e]:=y;next[e]:=head[x];head[x]:=e;

  end;

  procedure dfs(u,m:longint);

  var i,v:longint;

   begin

     inc(tot);

     left[u]:=tot;

     i:=head[u];

     while i> do

      begin

        v:=a[i];

        if v<>m then begin dfs(v,u); end;

        i:=next[i];

      end;

 //     inc(tot);

    right[u]:=tot;

   end;

  procedure build(u,l,r:longint);

   var mid:longint;

   begin

     if l=r then

      begin

       value[u]:=;

       exit;

      end;

      mid:=(l+r)>>;

      build(u*,l,mid);

      build(u*+,mid+,r);

      value[u]:=value[u*]+value[u*+];

   end;

   procedure upate(u,id,l,r:longint);//id 为修改点位置

    var mid:longint;

    begin

    if (l>id)or(r<id) then exit;

     if  (l=id)and(r=id) then

      begin

        if value[u]= then value[u]:= else value[u]:=;

        exit;

      end;

         mid:=(l+r)>>;

         upate(u*,id,l,mid);

         upate(u*+,id,mid+,r);

         value[u]:=value[u*]+value[u*+];

    end;

    function que(u,l,r,ql,qr:int64):int64;

    var mid:longint;

    begin

     if (ql>r)or(qr<l) then exit();

       if (ql<=l)and(r<=qr)  then exit(value[u]);

       mid:=(l+r)>>;

       exit(que(u*,l,mid,ql,qr)+que(u*+,mid+,r,ql,qr));

     end;

 begin

  readln(n);

  for i:= to n- do

   begin

     readln(x,y);

     add(x,y);

     add(y,x);

   end;

   dfs(,);

   build(,,tot);

   readln(k);

   for i:= to k do

    begin

      readln(ch,s);

      if ch='Q' then writeln(que(,,tot,left[s],right[s]))else

        begin

          upate(,left[s],,tot);

       //   upate(,right[s],,tot);

       end;

    end;

 end.

巴特西

dfs序线段树

最新文章

热门文章