dfs序+线段树
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 100500 #define maxe 200500 using namespace std; struct edge { int v,nxt; }e[maxe]; int n,m,x,y,nume=0,g[maxv]; int fath[maxv],w[maxv],mx[maxv],cnt=0; int ls[maxv<<2],rs[maxv<<2],val[maxv<<2],tot=0,root; char s[5]; void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void dfs(int x,int father) { w[x]=mx[x]=++cnt; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=father) { fath[v]=x; dfs(v,x); mx[x]=max(mx[x],mx[v]); } } } void build(int &now,int left,int right) { now=++tot;val[now]=right-left+1; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void pushup(int now) { val[now]=val[ls[now]]+val[rs[now]]; } int ask(int now,int left,int right,int l,int r) { if ((left==l) && (right==r)) return val[now]; int mid=(left+right)>>1; if (r<=mid) return ask(ls[now],left,mid,l,r); else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r); else return ask(ls[now],left,mid,l,mid)+ask(rs[now],mid+1,right,mid+1,r); } void modify(int now, int left,int right,int pos,int x) { if ((left==right) && (right==pos)) { val[now]=x; return; } int mid=(left+right)>>1; if (pos<=mid) modify(ls[now],left,mid,pos,x); else modify(rs[now],mid+1,right,pos,x); pushup(now); } int main() { scanf("%d",&n); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1,1); build(root,1,cnt); scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%s",s); if (s[0]=='C') { scanf("%d",&x); int regis=ask(root,1,n,w[x],w[x]); if (regis==0) modify(root,1,n,w[x],1); else modify(root,1,n,w[x],0); } else { scanf("%d",&x); printf("%d ",ask(root,1,n,w[x],mx[x])); } } return 0; }