POJ 3321：Apple Tree（dfs序+树状数组）

题目大意：对树进行m次操作，有两类操作，一种是改变一个点的权值（将0变为1，1变为0），另一种为查询以x为根节点的子树点权值之和，开始时所有点权值为1。

分析：

对树进行dfs，将树变为序列，记录每个点进栈出栈的时间戳作为其对应区间的左右端点，那么其子节点对应区间必在该区间内，对这段区间求和即可，用树状数组进行修改与求和。

代码：

program apple;

type

  point=^node;

   node=record

     x:longint; next:point;

   end;

var

  a:array[..]of point;

  bit:array[..]of longint;

  b,v1,v2:array[..]of longint;

  g:array[..]of boolean;

  n,i,m,d,x,y:longint; c:char;

procedure add(x,y:longint);

var p:point;

begin

  new(p); p^.x:=y;  p^.next:=a[x]; a[x]:=p;

end;

procedure dfs(x:longint);

var p:point;

begin

  inc(d); v1[x]:=d; g[x]:=true; new(p); p:=a[x];

  while p<>nil do

   begin

     if g[p^.x]=false then dfs(p^.x); p:=p^.next;

   end;

  inc(d); v2[x]:=d;

end;

procedure change(x:longint);

var i,y:longint;

begin

  y:=x;

  if b[x]= then i:= else i:=-;

  x:=v1[x];

  while (x<=*n) do

   begin inc(bit[x],i); inc(x,x and (-x));end;

  b[y]:=-b[y];

end;

function query(x:longint):longint;

var s:longint;

begin

  s:=;

  while x> do

   begin inc(s,bit[x]); dec(x,x and (-x)); end;

  exit(s);

end;

begin

  readln(n);

  for i:= to n- do

   begin

     readln(x,y);

     add(x,y);  add(y,x);

   end;

  d:=; dfs();

  for i:= to n do change(i);

  readln(m);

  for i:= to m do

   begin

     readln(c,x);

     if c='C' then change(x)

       else writeln(query(v2[x])-query(v1[x]-));

   end;

 end.

巴特西

POJ 3321：Apple Tree（dfs序+树状数组）

最新文章

热门文章