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
"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
Source
/*
这道题乍一看好像不能用树状数组来解决,后仔细想了想发现是可以的,
其实只需要将一棵树形结构映射成树状数组的下标范围即可
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;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745671
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1747400
数算的二叉树的POJ作业,分别有:二叉树1_二叉树的操作;二叉树2_文本二叉树;二叉树3_由中根序列和后根序列重建二叉树;二叉树4_表达式.表达式树.表达式求值;二叉树5_Huffman编码树;二叉树6_二叉搜索树;二叉树7_...
二叉树的应用,二叉树的应用,二叉树的应用,
北大POJ2255-Tree Recovery 解题报告+AC代码
poj 2201 Cartesian Tree.md
NULL 博文链接:https://128kj.iteye.com/blog/1746750
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了。 其实我写的就是线段树。很快,而且不到1k。
NULL 博文链接:https://128kj.iteye.com/blog/1757060
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......