秦皇岛房管局官网_福田区龙岗区发布通告_百度博客收录提交入口_百度网页高级搜索

题意

在kaka的房子外面有一棵苹果树。每到秋天，树上会长出很多苹果。kaka非常喜欢苹果，因此他一直在精心培育这棵大苹果树。

这棵树有N个叉，叉之间通过树枝连接。kaka将叉编号为1到N，根总是编号为1。苹果会在叉上生长，并且同一个叉上不会长出两个苹果。kaka想知道在一个子树中有多少个苹果，以研究苹果树的产量。

麻烦的是，有时一个新的苹果可能会在一个空叉上生长，而kaka可能会从树上摘下一个苹果作为甜点。你能帮助kaka吗？

代码

#include<iostream>
#define int long long
using namespace std;
int n,m;
int head[100005],nex[200005],to[200005],cnt = 0;
void add(int x,int y) {nex[++cnt] = head[x];head[x] = cnt;to[cnt] = y;
}
int mp[100005],ct = 0,ls[100005];
void dfs(int now,int fa) {mp[now] = ++ct;for(int i = head[now];i;i = nex[i]) {if(to[i] != fa) {dfs(to[i],now);}}ls[mp[now]] = ct;
}
int lowbit(int x) {return x & (-x);
} 
int c[1000005];
//修改函数 
void xiugai(int x,int y) {for(int i = x;i <= n;i += lowbit(i)) c[i] += y;return;
}
//查询第1-x的和 
int ask(int x) {int ans = 0;for(int i = x;i >= 1;i -= lowbit(i)) ans += c[i];return ans;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1;i < n;i++) {int x,y;cin >> x >> y;add(x,y),add(y,x);}dfs(1,1);for(int i = 1;i <= n;i++) xiugai(i,1);cin >> m;while(m--) {char x;int y;cin >> x >> y;y = mp[y];if(x == 'C') {if(ask(y) - ask(y - 1) == 1) xiugai(y,-1);else xiugai(y,1);}else {cout << ask(ls[y]) - ask(y - 1) << "\n";}}return 0;
}