传送门
Solution:
我们只需要采用和树链剖分近似的思想——把整个树的dfs序整理出来，排成线型。
这样一个节点的子树肯定是连续的一段，于是乎就可以用树状数组维护单点修改+区间查询的任务了。
#include<iostream> #include<cstdio> #define N 100005 using namespace std; int n,m,tot,first[N],in[N],out[N],sign,tree[N],exist[N]; struct Edge { int to,next; }edge[2*N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } inline void dfs(int now,int fa) { in[now]=++sign; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs(vis,now); } out[now]=sign; } inline int lowbit(int x) { return x&(-x); } inline void update(int x,int k) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=k; } inline int query(int x) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) ans+=tree[i]; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } dfs(1,0); for(int i=1;i<=n;i++) { update(in[i],1); exist[i]=1; } cin>>m; for(int i=1;i<=m;i++) { char ch; int x; cin>>ch>>x; if(ch=='Q') { cout<<query(out[x])-query(in[x]-1)<<'\n'; } if(ch=='C') { if(exist[x]) update(in[x],-1); else update(in[x],1); exist[x]^=1; } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9466942.html
