poj之旅：3321 Apple Tree

http://poj.org/problem?id=3321

这道题涉及到怎么把多叉树的查询转化为树状数组的前缀和查询 思想：通过某种办法将x转化为一个区间[L,R]； 一个连续的区间可以代表一棵子树

代码块语法遵循标准markdown代码，例如：

#include <iostream> #include <cstdio> #include <vector> using namespace std; /* id[i]编号为i的树杈对应的后序遍历次序 size[i]编号为i的树杈对应的子树规模 转化为BIT问题，i->[L,R]:R=id[i],L=R-size[i]+1 x[id[i]]代表是否有果 前缀和sum(id[i])代表所有后序遍历在id[i]之前的减少的苹果数量 */ int id[100010]={0},size[100010]={0}; int BIT[100010]={0},x[100010]={0}; typedef vector<int> ve; void postOrder(int subroot,vector<ve> &adj,bool book[],int& subsize,int &order){ //cout<<"traverse subroot "<<subroot<<endl; //subsize当前子树规模 bool leave=1;//当前树是否为叶子 for(int i=0;i<adj[subroot].size();i++){ if(!book[adj[subroot][i]]){ leave=0; book[adj[subroot][i]]=1; int tempsize=0;//子树返回的规模 postOrder(adj[subroot][i],adj,book,tempsize,order); //cout<<"tempsize "<<adj[subroot][i]<<": "<<tempsize<<endl; subsize+=tempsize; } } if (leave) { subsize=1; size[subroot]=1; } else{ subsize++; size[subroot]=subsize; } id[subroot]=++order; //cout<<"traverse subroot "<<subroot<<" end"<<endl; } void add(int,int,int); int Sum(int); int main(){ int n; cin>>n; //邻接表用于进行后序遍历 //vector<vector<int>> adj(n+1); vector<ve> adj(100002); for(int i=1;i<n;i++){ int f1,f2; scanf("%d%d",&f1,&f2); adj[f1].push_back(f2); adj[f2].push_back(f1); } //后序遍历 bool book[100010]={0}; book[1]=1; int tsize=0,order=0; postOrder(1,adj,book,tsize,order); /* for(int i=1;i<=n;i++){ cout<<"id "<<i<<": "<<id[i]<<endl; cout<<"size "<<i<<": "<<size[i]<<endl; } */ int m,fork; char ins; cin>>m; while(m--){ cin>>ins; cin>>fork; int postid=id[fork]; if(ins=='C'){ if(x[postid]==0){ x[postid]=1; add(postid,1,n); }else{ x[postid]=0; add(postid,-1,n); } /* for(int i=1;i<=n;i++){ cout<<"x["<<i<<"] "<<x[i]<<endl; cout<<"BIT["<<i<<"] "<<BIT[i]<<endl; } */ }else{ int sumR=Sum(postid); //cout<<"sumR: "<<sumR<<endl; int sumL=Sum(postid-size[fork]); //cout<<"sumL: "<<sumL<<endl; cout<<size[fork]-sumR+sumL<<endl; } } } void add(int i,int num,int n){ while(i<=n){ BIT[i]+=num; i=i+(-i&i); } } int Sum(int i){ int res=0; while(i>0){ res+=BIT[i]; i=i-(-i&i); } return res; }

不懂的地方：

有一个地方会卡超时：

vector<vector<int>> adj(100010);

这样就会超时，不知道为什么，有知道为什么的人可以解答一下。