POJ 3321-Apple Tree【树状数组+DFS序】

2023-08-17 17:33 388阅读 0赞

卡卡屋前有一株苹果树，每年秋天，树上长了许多苹果。卡卡很喜欢苹果。树上有*N*个节点，卡卡给他们编号1到*N*，根的编号永远是1.每个节点上最多结一个苹果。卡卡想要了解某一个子树上一共结了多少苹果。

现在的问题是不断会有新的苹果长出来,卡卡也随时可能摘掉一个苹果吃掉。你能帮助卡卡吗?

Input

输入数据：第一行包含一个整数*N*（*N* <= 100000）,表示树上节点的数目。  
接下来*N*\-1行，每行包含2个整数*u*和*v*，表示*u*和*v*是连在一起的。  
下一行包含一个整数*M*（*M* ≤ 100,000）.  
接下来*M*行包含下列两种命令之一：  
"**C *x***" 表示某个节点上的苹果发生了变化，如果原来没有苹果，则现在长出了一个苹果；如果原来有苹果，则是卡卡把它吃了。  
"**Q *x***" 表示查询*x*节点上的子树上的苹果有多少。包含节点*x*.

Output

对于每次查询，输出其结果。

思路：这题不难，就是通过dfs序来确定子树包含的节点，然后用树状数组来实现单点修改和区间查询就可以了，不过有些小细节需要注意一下。首先是会卡vector，开n个vector会超时，只能开一个二维vector才不会。另外记录dfs序后，在更新元素时是根据dfs序中的编号更新的，这点要注意一下。

#include<cstdio>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 1e5 + 10;
    const int mod = 1e9 + 7;
    vector<vector<int> > e(100010);
    int L[maxn], R[maxn], c[maxn], vis[maxn];
    int n, tot = 0;
    
    inline int lowbit(int i)
    {
        return (i & (-i));
    }
    void add(int i, int x)
    {
        while(i <= n)
        {
            c[i] += x;
            i += lowbit(i);
        }
    }
    int ask(int i)
    {
        int ret = 0;
        while(i > 0)
        {
            ret += c[i];
            i -= lowbit(i);
        }
        return ret;
    }
    void dfs(int u, int fa)
    {
        L[u] = ++tot;
        for(int i = 0; i < e[u].size(); ++i)
        {
            int v = e[u][i];
            if(v == fa) continue;
            dfs(v, u);
        }
        R[u] = tot;
    }
    
    int main()
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            add(i, 1);
        for(int i = 1; i < n; ++i)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1, 0);
        int m;
        scanf("%d", &m);
        while(m--)
        {
            char s[2];
            int x;
            scanf("%s%d", s, &x);
            if(s[0] == 'C')
            {
                int tmp = 1;
                vis[x] ^= 1;
                if(vis[x])
                    tmp = -1;
                x = L[x]; //这里要注意一下
                add(x, tmp);
            }
            else if(s[0] == 'Q')
            {
                printf("%d\n", ask(R[x]) - ask(L[x] - 1));
            }
        }
        return 0;
    }