Apple Tree
Description
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
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
题意：给出一颗树，对某个节点进行操作，如果有苹果，则摘；没有，则长个苹果。求某个节点拥有的苹果数量，每个节点最多只有一个苹果。
代码：
#include<stdio.h>
#include<stdlib.h>
#define maxn 100020
int low[maxn], high[maxn], n, c[maxn], t[maxn];
struct P
{
int pt, head;
}p[maxn];
struct N
{
int pt, id;
}node[maxn];
int th = 0, time = 0;
int create(int id)
{
th++;
node[th].pt = -1, node[th].id = id;
return th;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x, int y)
{
while (x <= n)
{
c[x] += y;
x += lowbit(x);
}
}
int sum(int x)
{
int s = 0;
while (x > 0)
{
s += c[x];
x -= lowbit(x);
}
return s;
}
void dfs(int root)
{
int v = p[root].head;
time++;//添加时间戳 ，就可以是问题转化为求区间和
low[root] = time;
for (v = p[root].head; v != -1; v = node[v].pt)
{
dfs(node[v].id);
}
high[root] = time;
}
int main()
{
int i, u, v, no, m, x, num;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
p[i].pt = -1, p[i].head = -1;
update(i, 1);
t[i] = 1;
}
num = n;
while (--num)
{
scanf("%d%d", &u, &v);
no = create(v);
node[p[u].pt].pt = no;
p[u].pt = no;
if (p[u].head == -1)
{
p[u].head = no;
}
}
dfs(1);
char a[2];
scanf("%d", &m);
while (m--)
{
scanf("%s%d", a, &x);
if (a[0] == 'Q')
{
printf("%d\n", sum(high[x]) - sum(low[x] - 1));
}
else
{
if (t[x])
{
update(low[x], -1);
t[x] = 0;
}
else
{
update(low[x], 1);
t[x] = 1;
}
}
}
system("pause");
return 0;
}
/*
5
1 2
1 3
3 4
3 5
*/