思路:
经典套路,通过dfs序将树上修改转化为线性修改,这样问题就转化为了单点修改,区间查询,用树状数组维护。
类似题
代码:
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const int maxn=1e5+100; struct BIT{ ll n,tr[maxn]; void init(){ memset(tr,0,sizeof tr); } ll lowbit(ll x){ return x&-x; } void update(ll pos,ll val){ while(pos<=n){ tr[pos]+=val;pos+=lowbit(pos); } } ll qask(ll pos){ ll res=0; while(pos){ res+=tr[pos];pos-=lowbit(pos); } return res; } }; int n,m,a[maxn]; vector<int>g[maxn]; ll in[maxn],out[maxn],timetmp; void dfs(int u,int fa){//dfs记录dfs序列 in[u]=++timetmp; for(int i=0;i<g[u].size();i++){ int j=g[u][i]; if(j==fa) continue; dfs(j,u); } out[u]=timetmp; } int main() { n=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); BIT t; t.n=1e5;t.init(); rep(i,1,n) t.update(in[i],1),a[i]=1; m=read; rep(i,1,m){ char op[2];int x; cin>>op;x=read; if(op[0]=='C'){ if(a[x]) t.update(in[x],-1); else t.update(in[x],1); a[x]=!a[x]; } else{ printf("%lld\n",t.qask(out[x])-t.qask(in[x]-1)); } } return 0; } /* **/