poj 3321Apple Tree解题报告

树状数组的题，只是要注意把深搜的时间戳当作是数组的下标，而且如果是根节点，为保证唯一性，结束时间和开始时间应该是一个值，而非根节点的结束时间应为所有根节点结束时间的最晚的

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define lowbit(x) (x)&(-x)
 5 #define N 100005
 6 using namespace std;
 7 int d[N],f[N],tim;
 8 bool used[N];
 9 int v[N];
10 int head[N],t;
11 int n;
12 void init()
13 {
14     memset(head,-1,sizeof(head));
15     memset(v,0,sizeof(v));
16     memset(used,0,sizeof(used));
17     t=0;
18     tim=0;
19 }
20 struct edge
21 {
22     int v,next;
23 };
24 edge e[N];
25 void add(int i,int x)
26 {
27     while(i<=n)
28     {
29         v[i]+=x;
30         i+=lowbit(i);
31     }
32 }
33 int getsum(int x)
34 {
35     int sum=0;
36     while(x>0)
37     {
38         sum+=v[x];
39         x-=lowbit(x);
40     }
41     return sum;
42 }
43 void add_edge(int u,int v)
44 {
45     e[t].v=v;
46     e[t].next=head[u];
47     head[u]=t++;
48 }
49 void dfs(int u)
50 {
51     d[u]=++tim;
52     int i,v;
53     for(i=head[u];i>=0;i=e[i].next)
54     dfs(e[i].v);
55     f[u]=tim;
56 }
57 int main()
58 {
59     int i,j,u,v,m;
60     char ch;
61     while(scanf("%d",&n)!=EOF)
62     {
63         init();
64         for(i=1;i<n;i++)
65         {
66             scanf("%d%d",&u,&v);
67             add_edge(u,v);
68             add(i,1);
69         }
70         add(n,1);
71         dfs(1);
72         scanf("%d",&m);
73         getchar();
74         while(m--)
75         {
76             scanf("%c%d",&ch,&u);
77             getchar();
78             if(ch=='C')
79             {
80                 if(used[u])
81                 add(d[u],1);
82                 else
83                 add(d[u],-1);
84                 used[u]=!used[u];
85             }
86             else
87             printf("%d\n",getsum(f[u])-getsum(d[u]-1));
88         }
89     }
90     return 0;
91 }