本文主要是介绍poj 3122 Apple Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
#include <iostream>
#include<cstring>
#include<cstdio>
#include<vector>using namespace std;
///直接开vector<int>mp[100005]会tle don't know why?
typedef vector<int >ve;
vector<ve>mp(100005);int forck[100005];
int c[100005];
int n;
int key;
int l[100005];
int r[100005];void dfs(int x)
{l[x]=key;int len=mp[x].size();for(int i=0;i<len;i++){key++;dfs(mp[x][i]);}r[x]=key;
}int lowbit(int x)
{return x&(-x);
}void add(int node,int num)
{while(node<=n){c[node]+=num;node+=lowbit(node);}
}
int Sum(int node)
{int sum=0;while(node>=1){sum+=c[node];node-=lowbit(node);}return sum;
}
int main()
{while(~scanf("%d",&n)){int a,b;for(int i=0;i<=n;i++)mp[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&a,&b);mp[a].push_back(b);}key=1;//cout<<"**"<<endl;dfs(1);//cout<<"*"<<endl;memset(c,0,sizeof(c));memset(forck,0,sizeof(forck));for(int i=1;i<=n;i++){forck[i]=1;add(i,1);}int m;char ch[5];int x;scanf("%d",&m);for(int i=0;i<m;i++){scanf("%s%d",ch,&x);if(ch[0]=='C'){if(forck[x]==1)add(l[x],-1);else add(l[x],1);forck[x]=!forck[x];}else{int sum;sum=Sum(r[x])-Sum(l[x]-1);printf("%d\n",sum);}}}return 0;
}
第一次开树状数组的题，看了一个星期的树状数组，但是对此还是没有真正理解，只是知道大体是怎样的过程 惭愧啊，写这个题也是先看了一下大神的题解，一个是不知道怎么建数组，dfs;另一个是学习一下树状数组怎么用，通过这个题也算明白了怎么用，然后自己根据思路写了一边。不过tle了好几次，最后看了讨论才知道不能直接开vector 但不知为什么- -；
这篇关于poj 3122 Apple Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
