pku3321 Apple Tree

给你一颗苹果树，树的主干设为1，每一个分支设为一个数，一直到N，代表这颗苹果树。每个分支上面只能最多有一个苹果。

下面是两种操作，Q 和C

C j 的意思是如果 j 这个枝上面有苹果就摘下来，如果没有，那么就会长出新的一个

Q j 就是问 j 这个叉上面的苹果总数。

先一遍DFS确定树的形态，再一遍DFS求出每各节点标号后作为根的子树标号范围，有DFS性质，这个范围一定连续，

接下来问题转化为在某一个点加一或减一，查询区间和，用树状数组完成。

View Code

  1 program pku3321(input,output);
  2 type
  3    node     = ^link;
  4    link     = record
  5           goal : longint;
  6           next : node;
  7        end;       
  8 var
  9    l,tree  : array[0..100100] of node;
 10    v       : array[0..100100] of boolean;
 11    x,y,dfn : array[0..100100] of longint;
 12    c       : array[0..100100] of longint;
 13    n,q,cnt : longint;
 14 procedure add(xx,yy: longint );
 15 var
 16    tt : node;
 17 begin
 18    new(tt);
 19    tt^.next:=l[xx];
 20    tt^.goal:=yy;
 21    l[xx]:=tt;
 22 end; { add }
 23 function max(aa,bb :longint ):longint;
 24 begin
 25    if aa>bb then
 26       exit(aa);
 27    exit(bb);
 28 end; { max }
 29 function min(aa,bb : longint ):longint;
 30 begin
 31    if aa<bb then
 32       exit(aa);
 33    exit(bb);
 34 end; { min }
 35 procedure add_tree(xx,yy :longint );
 36 var
 37    tt : node;
 38 begin
 39    new(tt);
 40    tt^.goal:=yy;
 41    tt^.next:=tree[xx];
 42    tree[xx]:=tt;
 43 end; { add_tree }
 44 procedure init;
 45 var
 46    i,xx,yy : longint;
 47 begin
 48    readln(n);
 49    for i:=1 to n-1 do
 50    begin
 51       readln(xx,yy);
 52       add(xx,yy);
 53       add(yy,xx);
 54    end;
 55    cnt:=0;
 56    readln(q);
 57    fillchar(v,sizeof(v),false);
 58 end; { init }
 59 procedure dfs1(now :longint );
 60 var
 61    t : node;
 62 begin
 63    v[now]:=true;
 64    t:=l[now];
 65    while t<>nil do
 66    begin
 67       if not v[t^.goal] then
 68       begin
 69      add_tree(now,t^.goal);
 70      dfs1(t^.goal);
 71       end;
 72       t:=t^.next;
 73    end;
 74 end; { dfs1 }
 75 procedure dfs(now :longint );
 76 var
 77    t : node;
 78 begin
 79    inc(cnt);
 80    dfn[now]:=cnt;
 81    x[now]:=cnt;
 82    y[now]:=cnt;
 83    t:=tree[now];
 84    while t<>nil do
 85    begin
 86       dfs(t^.goal);
 87       x[now]:=min(x[now],x[t^.goal]);
 88       y[now]:=max(y[now],y[t^.goal]);
 89       t:=t^.next;
 90    end;
 91 end; { dfs }
 92 function lowbit(x :longint ):longint;
 93 begin
 94    exit(x and(-x));
 95 end; { lowbit }
 96 procedure adds(now,w :longint );
 97 begin
 98    while now<=n do
 99    begin
100       inc(c[now],w);
101       now:=now+lowbit(now);
102    end;
103 end; { adds }
104 function find(now : longint ):longint;
105 begin
106    find:=0;
107    while now>0 do
108    begin
109       inc(find,c[now]);
110       now:=now-lowbit(now);
111    end;
112 end; { find }
113 procedure main;
114 var
115    ch       : char;
116    xx,i : longint;
117 begin
118    for i:=1 to n do
119       adds(i,1);
120    fillchar(v,sizeof(v),true);
121    for i:=1 to q do
122    begin
123       read(ch);
124       case ch of
125     'C' : begin
126        readln(xx);
127        v[xx]:=not v[xx];
128        if not v[xx] then
129           adds(dfn[xx],-1)
130        else
131           adds(dfn[xx],1);
132     end;
133     'Q' : begin
134        readln(xx);
135        writeln(find(y[xx])-find(x[xx]-1));
136     end;
137       end; { case }
138    end;
139 end; { main }
140 begin
141    init;
142    dfs1(1);
143    dfs(1);
144    main;
145 end.