其实这道题和以前在poj上做过的将树映射到树状数组的题目很像

首先不难想到,将一条边从土路修成公路,只对以这条边连接的孩子结点为根的子树有影响;

于是和之前那道poj的题目很像,后序遍历树,对每个节点重标号,每个点初始值就是深度

下面的问题就变成了:

土路修成公路---->区间修改

查询从点1到某个点所经过的土路数----->单点求值;

这种问题我们其实可以用树状数组来做;

a[i]表示原数组的值;

令c[i]=a[i]-a[i-1],特殊的c[1]=a[1];

然后我们对c数组做树状数组

区间修改(假设是[l,r]都+1)就是c[l]+1,c[r+1]-1;

单点求值就是求signma(c[1~i])

当然后来知道其实用dfs序更简单

 type node=record
       point,next:longint;
     end; var fa,a,c,p,r,h,d:array[..] of longint;
    edge:array[..] of node;
    len,n,m,x,y,t,i:longint;
    ch:char; procedure add(x,y:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].next:=p[x];
    p[x]:=len;
  end; function lowbit(x:longint):longint;
  begin
    exit(x and (-x));
  end; procedure work(x,f:longint);
  begin
    while x<=n do
    begin
      inc(a[x],f);
      x:=x+lowbit(x);
    end;
  end; function ask(x:longint):longint;
  begin
    ask:=;
    while x> do
    begin
      ask:=ask+a[x];
      x:=x-lowbit(x);
    end;
  end; procedure dfs(x,d:longint);
  var i,y,tmp:longint;
  begin
    i:=p[x];
    c[x]:=d;
    tmp:=n+;
    while i<>- do
    begin
      y:=edge[i].point;
      if (c[y]=) and (y<>) then
      begin
        fa[y]:=x;
        dfs(y,d+);
        if tmp>h[y] then tmp:=h[y];
      end;
      i:=edge[i].next;
    end;
    inc(t);
    r[x]:=t;
    if tmp=n+ then h[x]:=r[x]
    else h[x]:=tmp;
  end; begin
  len:=-;
  fillchar(p,sizeof(p),);
  readln(n);
  for i:= to n- do
  begin
    readln(x,y);
    add(x,y);
    add(y,x);
  end;
  t:=;
  dfs(,);
  for i:= to n do
    d[r[i]]:=c[i];
  for i:= to n do
    work(i,d[i]-d[i-]);
  work(,d[]);
  readln(m);
  for i:= to n+m- do
  begin
    read(ch);
    if ch='W' then
    begin
      readln(x);
      writeln(ask(r[x]));
    end
    else begin
      readln(x,y);
      if fa[x]=y then t:=x else t:=y;
      work(h[t],-);
      work(r[t]+,);
    end;
  end;
end.
05-08 15:26