本文主要是介绍poj - 3321 - Apple Tree（dfs+线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一棵苹果树有n个结点，开始时每个结点有一个苹果，这n个结点由m条枝连起来，现执行以下两种操作，C x：如果结点x原来有苹果，则把它摘掉，如果没有，则长出1个苹果。Q x：询问以x为根的树的苹果共几个？
题目链接：http://poj.org/problem?id=3321
——>>求一棵子树的和，转化为求一个连续区间的和。用线段树进行维护，时间复杂度为O(max(N, M*log(N)))。。
#include <cstdio>
#include <cstring>using namespace std;#define lc (o<<1)
#define rc ((o<<1)|1)const int maxn = 100000 + 10;int l[maxn], r[maxn], dfs_clock;
int hed[maxn], v[maxn<<1], nxt[maxn<<1], ecnt;
int sum[maxn<<2];void init() {memset(hed, -1, sizeof(hed));ecnt = 0;dfs_clock = 1;
}void add_edge(int uu, int vv) {v[ecnt] = vv;nxt[ecnt] = hed[uu];hed[uu] = ecnt++;
}void dfs(int x, int f) {l[x] = dfs_clock;for(int e = hed[x]; e != -1; e = nxt[e]) {int vv = v[e];if(vv != f) dfs(vv, x);}r[x] = dfs_clock++;
}void build(int o, int L, int R) {if(L == R) {sum[o] = 1;return;}int M = (L + R) >> 1;build(lc, L, M);build(rc, M+1, R);sum[o] = sum[lc] + sum[rc];
}void update(int o, int L, int R, int x) {if(L == R) {sum[o] ^= 1;return;}int M = (L + R) >> 1;if(x <= M) update(lc, L, M, x);else update(rc, M+1, R, x);sum[o] = sum[lc] + sum[rc];
}int query(int o, int L, int R, int ql, int qr) {if(ql <= L && R <= qr) return sum[o];int M = (L + R) >> 1;int ans = 0;if(ql <= M) ans += query(lc, L, M, ql, qr);if(qr > M) ans += query(rc, M+1, R, ql, qr);return ans;
}int main()
{char op;int N, a, b, M, x;while(scanf("%d", &N) == 1) {init();for(int i = 1; i < N; i++) {scanf("%d%d", &a, &b);add_edge(a, b);add_edge(b, a);}dfs(1, -1);build(1, 1, N);scanf("%d", &M);while(M--) {getchar();scanf("%c%d", &op, &x);if(op == 'C') update(1, 1, N, r[x]);else printf("%d\n", query(1, 1, N, l[x], r[x]));}}return 0;
}这篇关于poj - 3321 - Apple Tree（dfs+线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
