题目描述

一个有n个节点的树，树的每个节点可能有一个苹果或没有，有两种操作：
C x 将节点x的权值改变，即如果有一个苹果删掉，否则增加一个苹果。
Q x 询问以节点x为根的子树中有多少个苹果。

思路

题目中要动态的修改和输出
可以用树状数组进行区间统计的优化，然后先跑一边dfs求出每个子树的开头和结尾

#include 
#include 
int f[100001],a[100001],s[100001],e[100001];
int t[100001][101],n;
int add(int x,int y)
{
    while (x<=n)
    {
        f[x]+=y;
        x+=(x&(-x));
    }
    return 0;
}   
int count(int x)
{
    int ans=0;
    while (x>=1)
    {
        ans+=f[x];
        x-=(x&(-x));
    }
    return ans;
}
int dep=0;
int dfs(int x)
{
    dep++;
    s[x]=dep;
    for (int i=1;i<=t[x][0];i++)
        dfs(t[x][i]);
    e[x]=dep;
    return 0;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        t[x][0]++;
        t[x][t[x][0]]=y;
    }
    dfs(1);
    for (int i=1;i<=n;i++)
    {
        a[i]=1;
        add(i,a[i]);
    }
    int m;
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        char ch[3];
        scanf("%s",ch);
        int x;
        scanf("%d",&x);
        if (ch[0]=='C')
        {
            a[x]=-a[x];
            add(s[x],a[x]);
        }
        else 
        {
            printf("%d\n",count(e[x])-count(s[x]-1));
        }
    }
    return 0;
}