`
bobten2008
  • 浏览: 11148 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

POJ 3321 Apple Tree 【二叉树结点个数的统计也可以用树状数组来做】

阅读更多

Apple Tree
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 7907   Accepted: 2194

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
"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
"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

Source

POJ Monthly--2007.08.05, Huang, Jinsong
/*
这道题乍一看好像不能用树状数组来解决,后仔细想了想发现是可以的,
其实只需要将一棵树形结构映射成树状数组的下标范围即可
1)首先需要利用邻接表来建树
2)然后对这棵树进行先序遍历并给各个节点重新赋值下标,同时算出当
前节点及其子树的最小(其实就是自己的新下标)和最大下标,那么当前
节点所涵盖的范围就是[最小下标,最大下标]了
3)建立树状树状,每个节点初值利用modify加1(因为初始每个节点都有
苹果).对于原结点i进行修改操作,只需调用modify(i的最小下标)即可;
对于原始结点i进行查询操作,只需调用sum(i的最大下标) - sum(i的最小下标-1)即可,
其实画个图就很明白了.
*/
#include <iostream>
#define MAX_N 100000
using namespace std;
struct edge
{
    int fromId, to;
    edge *next;
    edge()
    {
        fromId = to = 0;
        next = NULL;
    }
}*head[MAX_N + 5];
bool has[MAX_N + 1];
int count[MAX_N + 1];
int idLH[MAX_N + 1][2];
int num, curId = 0;
void addEdge(int from, int to)
{
    edge *ne = new edge();
    ne->fromId = from;
    ne->to = to;
    ne->next = head[from];
    head[from] = ne;
}
int dfsGetId(int id)
{
    idLH[id][0] = ++curId;
    edge *ne = head[id];
    int highId = INT_MIN;
    if(curId > highId) highId = curId;
    while(ne != NULL)
    {
        if((curId = dfsGetId(ne->to)) > highId) highId = curId;
        ne = ne->next;
    }
    idLH[id][1] = highId;
    return highId;
}
int lowerbit(int n)
{
    return n & (n ^ (n - 1));
}
void modify(int n, int val)
{
    int i;
    for(i = n; i <= num; i += lowerbit(i))
        count[i] += val;
}
int sum(int n)
{
    int i;
    int res = 0;
    for(i = n; i >= 1; i -= lowerbit(i))
        res += count[i];
    return res;
}
int main()
{
    int i, from, to;
    scanf("%d", &num);
    for(i = 1; i < num; i++)
    {
        scanf("%d%d", &from, &to);
        addEdge(from, to);
    }
    int temp = dfsGetId(1);
    for(i = 1; i <= num; i++)
    {
        has[i] = true;
        modify(i, 1);
    }
    int qNum, dest;
    char type;
    scanf("%d", &qNum);
    for(i = 1; i <= qNum; i++)
    {
        getchar();
        scanf("%c%d", &type, &dest);
        if(type == 'C')
        {
            if(has[dest]){ has[dest] = false; modify(idLH[dest][0], -1);}
            else {has[dest] = true; modify(idLH[dest][0], 1);}
        }
        else 
        {
            int res1 = sum(idLH[dest][1]);
            int res2 = sum(idLH[dest][0] - 1);
            printf("%d\n", res1 - res2);
        }
    }
    return 0;
}
 

分享到:
评论

相关推荐

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    树状数组练习:POJ 3067

    树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。 POJ 3067题目大致是这样的:给定一...

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    二维树状数组学习之二:练习POJ 1195

    当收到一个查询请求时,我们使用二维树状数组来计算指定矩形区域的和。由于树状数组的性质,这些操作的时间复杂度可以达到 O(log m + log n),这比直接遍历矩阵的 O(mn) 时间复杂度要快得多。 以下是Main.java的...

    poj 2352 stars(树状数组,线段树)

    POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇文章中,我们将详细介绍如何利用树状数组和线段树来解决这个问题...

    二维树状数组练习 POJ 2029

    它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...

    树状数组(Binary Indexed Tree)

    - **解法**:可以考虑使用树状数组来维护区间内的最值,通过低比特操作实现高效更新和查询。 7. **二维树状数组 POJ2155:Matrix** - **题意**:给定一个n*n的矩阵,支持对子矩阵进行翻转操作,并查询特定位置的...

    树状数组题解1

    树状数组,又称线段树(Segment Tree),是一种用于高效解决区间查询与修改问题的数据结构。在上述题目中,树状数组被广泛应用于各种不同的场景,如星星坐标的等级计算、矩阵操作、序列排序优化以及线路交叉点的计算...

    POJ2255-Tree Recovery

    【标题】"POJ2255-Tree Recovery" 是一个来自北京大学在线判题系统POJ(Problem Set of Peking University)的编程题目。这个题目主要涉及到数据结构和图论的知识,尤其是树的恢复问题。 【描述】"北大POJ2255-Tree...

    数算POJ二叉树作业

    数算的二叉树的POJ作业,分别有:二叉树1_二叉树的操作;二叉树2_文本二叉树;二叉树3_由中根序列和后根序列重建二叉树;二叉树4_表达式.表达式树.表达式求值;二叉树5_Huffman编码树;二叉树6_二叉搜索树;二叉树7_...

    ACM数据结构之树状数组和线段树

    ### ACM数据结构之树状数组和线段树 #### 线段树 线段树是一种非常有效的数据结构,主要用于解决区间查询问题。它能够快速地处理区间内的各种操作,如查询、修改等。 ##### 线段树的定义与特性 线段树本质上是一...

    滚动数组应用:POJ 1159

    描述中提到的链接指向了一篇博客文章,尽管具体内容没有提供,但可以推测博主分享了他们如何使用滚动数组来解决POJ 1159问题的思路和源代码。通常,这类博客会包含对问题的解析、动态规划的状态转移方程以及如何利用...

    POJ3468.zip_poj3468

    在解决POJ3468这个题目时,参赛者可能需要理解并熟练运用树状数组来处理区间操作。例如,题目可能给出一个数组和一系列的指令,指令包括两种类型:一种是将某个区间内的所有元素都加上一个常数值,另一种是询问某一...

    poj 2418 二叉树

    二叉树的应用,二叉树的应用,二叉树的应用,

    poj1990.rar_POJ 19_poj_poj19

    本篇文章将深入探讨该题目的解决方案,特别是如何巧妙运用两个树状数组来优化算法,提高效率。 首先,我们要理解树状数组(也称作线段树)这一数据结构。树状数组是一种用于高效处理区间查询和修改的结构,其基础是...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    但是,可以使用其他数据结构,如动态数组(std::vector)或者通过创建新的大数组,复制原有元素,然后释放旧数组来模拟数组的扩充。 "poj_2682(3).cpp"是一个可能包含解决方案的C++源代码文件。通常在编程竞赛中,...

    poj 2201 Cartesian Tree.md

    poj 2201 Cartesian Tree.md

    ACM-POJ 算法训练指南

    1. **高级数据结构**:如树状数组、线段树(poj2528, poj2828, poj2777, poj2886, poj2750)。 2. **平衡树**:如AVL树、红黑树等(poj2482, poj2352)。 3. **并查集**:用于处理不相交集合的问题(poj1195, poj...

Global site tag (gtag.js) - Google Analytics