树状数组-DFS序-Apple Tree
题目链接
https://www.cnblogs.com/gj-Acit/p/3236843.html
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
题意：
就是一棵苹果树，二叉树；
树有N个叉子，它们通过分支连接。卡卡将叉子编号为1到N，根始终编号为1.苹果将在叉子上生长，两个苹果不会在同一个叉子上生长。
C x”表示叉x上的苹果存在已经改变。即如果叉子上有苹果，那么卡卡就会选择它;否则一个新的苹果在空叉上长大。
“Q x”表示查询fork x上方子树中的苹果数量，包括叉子x上的苹果（如果存在）
注意树的开头是苹果
对于每个查询，输出每行的相应答案。
按照题意来说，就是对树上节点的更新和查询求和，不同的是，查询时，我们是对于x位置上方的苹果的数量，比如下图，我们对于位置x是c[4],那么我们要得到的值是 c[4]+c[8];
解题思路：
理解了题意，明显就可以知道是用树状数组，或者是线段树应该也可以。
当然，这题是要用到dfs序.
那我们在这里就讲一下什么是树的dfs序；简单的说就是DFS时遍历的顺序；
DFS序就是将树形结构转化为线性结构，用dfs遍历一遍这棵树，进入到x节点有一个up时间戳，递归退出时有一个out 时间戳，x节点的两个时间戳之间遍历到的点，就是根为x的子树的所有节点，他们的dfs进入的时间戳是递增的。同时两个时间戳构成了一个区间，x节点在这段区间的最左端，这个区间就是一棵根节点为x的子树，对于区间的操作就是其他维护方式的应用了。
时间戳：是一份能够表示一份数据在一个特定时间点已经存在的完整的可验证的数据；
比如下图：
1：建树，这里数据比较大，我们可以用一个容器vector
2：dfs序
3.树状数组常规操作
4：输入，输入；
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
const int num=100005;
vector<vector<int> > g(num);//C++ g(num) 即g[num];//这个用vector<int>g(num)会超时
int up[num],out[num];//进入的时间戳 //出去的时间戳
bool mark[num];//还有这个bool 而不能用int 用int会wa；
int time,n;
int tree[num];
void dfs(int k,int befk)//dfs序
{
up[k]=++time;
for(int i=0; i<g[k].size(); i++)
{
if(g[k][i]==befk)
continue;
dfs(g[k][i],k);
}
out[k]=time;
}
int lowbit(int x)
{
return x&-x;
}
void udpute(int x,int val)
{
while(x<=n)
{
tree[x]+=val;
x+=lowbit(x);
}
}
int ask(int a)
{
int sum=0;
while(a>0)
{
sum+=tree[a];
a-=lowbit(a);
}
return sum;
}
int main()
{
char ws[2];
int a,b;
int m;
scanf("%d",&n);
memset(mark,true,sizeof(mark));
for(int i=1; i<=n-1; i++)
{
scanf("%d %d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,-1);//dfs序；
for(int i=1; i<=n; i++)//
{
tree[i]=lowbit(i);
}
scanf("%d",&m);
for(int i=0; i<m; i++)
{
scanf("%s %d",ws,&a);
if(ws[0]=='Q')
{
printf("%d\n",ask(out[a])-ask(up[a]-1));//ask
}
else
{
if(mark[a]==false)
udpute(up[a],1);
else
udpute(up[a],-1);
mark[a]^=1;//
}
}
return 0;
}
