- #include
- #include
- #include
- #include using namespace std;
- struct T_tree {
- int l,r,dis;
- };
- structT_tree tree[400001];
- struct T_edge {
- int from,to,next;
- };
- structT_edge edge[100001];
- struct T_interval {
- int li,ri;
- };
- structT_interval find_[100001];
- intn,m,num_edge=0,head[100001],tot=0;
- inline voidedge_add(int from,int to)
- {
- num_edge++;
- edge[num_edge].to=to;
- edge[num_edge].from=from;
- edge[num_edge].next=head[from];
- head[from]=num_edge;
- }
- voiddfs(int now)
- {
- tot++;
- find_[now].li=tot;
- for(inti=head[now];i;i=edge[i].next)
- {
- dfs(edge[i].to);
- }
- find_[now].ri=tot;
- }
- voidtree_up(int now)
- {
- tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis;
- }
- voidtree_build(intnow,intl,int r)
- {
- tree[now].l=l,tree[now].r=r;
- if(l==r)
- {
- tree[now].dis=1;
- return ;
- }
- intmid=(l+r)>>1;
- tree_build(now<<1,l,mid);
- tree_build(now<<1|1,mid+1,r);
- tree_up(now);
- return ;
- }
- voidtree_change(intnow,int to)
- {
- if(to==tree[now].l&&tree[now].r==to)
- {
- if(tree[now].dis) tree[now].dis=0;
- elsetree[now].dis=1;
- return ;
- }
- intmid=(tree[now].l+tree[now].r)>>1;
- if(to>mid) tree_change(now<<1|1,to);
- elsetree_change(now<<1,to);
- tree_up(now);
- }
- inttree_query(intnow,intl,int r)
- {
- if(tree[now].l==l&&tree[now].r==r)
- {
- return tree[now].dis;
- }
- intmid=(tree[now].l+tree[now].r)>>1;
- if(l>mid)returntree_query(now<<1|1,l,r);
- else if(r<=mid)returntree_query(now<<1,l,r);
- else returntree_query(now<<1,l,mid)+tree_query(now<<1|1,mid+1,r);
- }
- int main()
- {
- scanf("%d",&n);
- int from,to;
- for(inti=1;i)
- {
- scanf("%d%d",&from,&to);
- edge_add(from,to);
- }
- dfs(1);
- tree_build(1,1,n);
- scanf("%d",&m);
- char t_do;
- int to_ch;
- for(inti=1;i<=m;i++)
- {
- //scanf("%c %d",&t_do,&to_ch);
- //scanf("%c",&t_do);
- //scanf("%d",&to_ch);cin>>t_do>>to_ch;
- if(t_do=='Q') printf("%d\n",tree_query(1,find_[to_ch].li,find_[to_ch].ri));
- elsetree_change(1,find_[to_ch].li);
- }
- return 0;
- }
来源: