题意：一开始1-n都有苹果，Q查询以x为根下存在多少。

树状数组+DFS+队列转换

这题纠结了2天，一开始一点思路都没有，看大神都是吧树状数组转换成队列来做

看了好久都不知道怎么转换的，

解决方法：用两个队列，一个是以记录(s,u),s为起点，一个记录s,为终点

用DFS查找一棵分支，记录访问次序，这样就可以转换成树状数组了

 

#include 
    
      //参照大神的代码#include 
     
      using namespace std;#define N 500000int tree[N],b[N],e[N],head[N];  //b记录DFS访问的次序，e表示当前节点DFS的最后一个节点标号bool h[N],v[N]; //v[i]表示是否被访问过int num;struct node{    int x,next;}a[N];inline int lowbit(int x) {return x&-x;}void update(int x,int t){    int n;    if(h[t]) {h[t]=false;n=-1;} //false 表示没有    else {h[t]=true;n=1;}    while(x<=num)    {        tree[x]+=n;        x+=lowbit(x);    }}int getsum(int x){    int ans=0;    while(x>0)    {        ans+=tree[x];        x-=lowbit(x);    }    return ans;}void dfs(int x){    v[x]=true;    b[x]=++num;    for(int i=head[x];i!=-1;i=a[i].next)    {        if(!v[a[i].x])            dfs(a[i].x);    }    e[x]=num;  //printf("%d  %d %d\n",x,num,b[x]);}int main(){    int n,i,j;    while(scanf("%d",&n)!=EOF)    {        int m=0;        memset(tree,0,sizeof(tree));        memset(head,-1,sizeof(head));        for(i=1;i