题目：http://poj.org/problem?id=3321
动态更新某个元素，并且求和，显然是二叉索引树，但是节点的标号不连续，二叉索引树必须是连续的，所以需要转化成连续的，多叉树的形状已经建好，只要重新标号成连续的就行了。
感觉重新标号是这个题最难的地方，否则就是个纯水题了。。。
重新标号是看的别人的。。。用dfs遍历多叉树标号。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> int item = ;
int c[], n;
int start[], end[]; struct Tree
{
int num;
struct Tree *next;
Tree()
{
next = NULL;
num = ;
}
}tree[]; int lowbit(int x)
{
return x & (-x);
} void add(int x, int y)
{
while(x <= n)
{
c[x] += y;
x += lowbit(x);
}
} int sum(int x)
{
int ret = ;
while(x)
{
ret += c[x];
x -= lowbit(x);
}
return ret;
} int query(int x, int y)
{
return sum(y) - sum(x-);
} void dfs(int x)
{
start[x] = ++item;
struct Tree *p = tree[x].next;
while(p != NULL)
{
if(start[p->num] == )
dfs(p->num);
p = p->next;
}
end[x] = item;
} int main()
{
int u, v;
scanf("%d", &n);
memset(tree, , sizeof(tree));
memset(start, , sizeof(start));
memset(c, , sizeof(c));
for(int i = ; i < n; i++)
{
scanf("%d %d", &u, &v);
struct Tree *p = new Tree;
p->num = v;
p->next = tree[u].next;
tree[u].next = p;
}
dfs();
for(int i = ; i <= n; i++)
{
add(i, );
}
int q, z;
char cmd[];
scanf("%d", &q);
while(q--)
{
scanf("%s %d", cmd, &z);
if(cmd[] == 'Q')
{
printf("%d\n", query(start[z], end[z]));
}
else
{
if(sum(start[z]) - sum(start[z]-) == )
add(start[z], -);
else add(start[z], );
}
}
return ;
}