POJ 3321 apple tree

题意

在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;
}

原文地址：https://blog.csdn.net/guozhetao/article/details/144791031

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！