首页 > 代码库 > TreeArray3321_DFS
TreeArray3321_DFS
题意：有一棵树，树上有一些节点，每个节点上刚开始都有一个苹果，对每个节点可以有两种操作，若刚开始有苹果，则变为没苹果，若刚开始没苹果，则变为有一个苹果。有多次操作，有多次询问，对于每次询问，回答该结点以及该结点以上有多少个苹果。
输入是节点之间的关系，
1 2
1 3
表示节点1和节点2直接存在树枝相连
假设有上图形式的情况。求点2以上节点的之和时，如果把3算进去便是错误的，因此需要用DFS把各个点的后序重新排序，同时标记每个几点的管辖范围。
一个节点的第一次被DFS访问到DFS结束（每个节点结束的时候，时间戳加1）这段时间内的点就是该点管辖的区域。
DFS访问的顺序为：1 3 5 2 4，根据时间戳的后序重新排列节点
得到各个节点的low,high值分别为
5:【1 1】 3：【1 2】 4:【3 3】 2【3 4】 1【1 5】
按照后序得到的元素顺序为 5 3 4 2 1 ，该顺序也是最终的树状数组顺序
这样求2节点以上节点之和时用sum[4]-sum[2]
修改的时候，从该点开始（该点在映射后的顺序为后序），然后修改该节点的父节点直到N。
由于DFS特点，2和3不在一个分支上，所以使得两者第一次访问的low值不一样，3,5在一个线上，因此LOW值相同。
用app数组标记节点上目前是否有苹果，用c数组是对app数组的树状化处理。
初始时，每个节点都有苹果，而树状数组每个元素涵盖了2^k个元素，每个元素一个苹果，（即便c数组是映射以后的数组，即顺序并不是1 2 3 4 5，而是5 3 4 2 1，但是每个元素起始都是1，因此管辖区域总和仍然是2^k）因此共有2^k个苹果，C数组初始化为for(i=1;i<=n;i++)c[i]=lowbit(i);c[i]=lowbit(i)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100005
struct Edge{
int v,next;//v记录边头部，next记录下一边
}edge[MAXN];
struct Range{//存每个节点范围
int low,high;
}range[MAXN];
int root[MAXN];// root[u]以u为根的节点编号
int c[MAXN];
int app[MAXN];//the state of point
int index,n,m;
inline void addEdge(int u,int v){//加边，将节点插入头部
edge[index].v=v; //这里的邻接表表示的是单向边，因此不需要设置visit数组
edge[index].next=root[u];
root[u]=index++;
}
inline void dfs(int u){//后序遍历
range[u].low=index;//记录最小编号
if(root[u]==-1){
range[u].high=index++;
return;
}
else {
for(int i=root[u];i!=-1;i=edge[i].next){
dfs(edge[i].v);
}
}
range[u].high=index++;//记录最大编号，即根的编号
}
inline int lowbit(int x){
return x&(-x);
}
inline void update(int i,int v){
while(i<=n){
c[i]+=v;
i+=lowbit(i);
}
}
inline int getsum(int i){
int sum=0;
while(i>0){
sum+=c[i];
i-=lowbit(i);
}
return sum;
}
int main(){
int i,j;
int u,v;
char cmd;
while(scanf("%d",&n)==1){
memset(root,-1,sizeof(root));
index=1;
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
fill(app,app+n+5,1); //表示每个节点开始都有苹果在上面
for(i=1;i<=n;i++)c[i]=lowbit(i);//初始化，一开始每个节点都有 apple
index=1;
dfs(1);
scanf("%d",&m);
while(m--){
scanf(" %c%d",&cmd,&u);//不用getchar，用scanf里面加空格的方式也可以消除回车
if(cmd==‘C‘){
int val=1;
if(app[u])val=-1; //本来有苹果 现在要摘掉
app[u]=!app[u];
update(range[u].high,val); //父节点都要加上val
}
else {
int val=getsum(range[u].high)-getsum(range[u].low-1);
printf("%d\n",val);
}
}
}
return 0;
}
TreeArray3321_DFS