POJ3321 Apple Tree 题解

POJ3321 Apple Tree

线段数例题解析合集

题意：给定一棵树，有两种操作：1、把某个节点上的数^1(若是1改为0，是0改为1) 2、查询以某个节点为根节点的子树中1的个数

在一棵树上进行单点修改和查询，只要进行一遍dfs，记录每个点的dfs序即可把问题转化到链上用线段树进行维护

更改和模板一样，查询时以每棵子树遍历时第一个节点的dfs序和最后一个节点的边界作为查询区间（每颗子树中节点的DFS序是连续的）

#include <stdio.h>
#include <iostream>
using namespace std;
inline void read (int &x) {
    char ch = getchar(); x = 0;
     while (!isdigit(ch)) ch = getchar();
     while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
void print (int x) {
    if (x > 9) print (x / 10);
    putchar (x % 10 + 48);
}
const int N = 1e6 + 10;
int n, cnt, tot, m, pos, ql, qr, s[N << 2], num[N], l[N], r[N], nxt[N << 1], to[N << 1], h[N];
inline void add (int u, int v) {
    to[++tot] = v, nxt[tot] = h[u], h[u] = tot;
}
void dfs (int u, int la) {
    num[u] = l[u] = ++ cnt;
    for (int i = h[u]; i; i = nxt[i]) if (to[i] != la) dfs (to[i], u);
    r[u] = cnt;  //l、r记录每颗子树中最小和最大的dfs序
}
#define ls p << 1
#define rs p << 1 | 1
void build (int p, int l, int r) {
    if (l == r) {s[p] = 1; return;}
    int mid (l + r >> 1);
    build (ls, l, mid), build (rs, mid + 1, r);
    s[p] = s[ls] + s[rs];
}
void change (int p, int l, int r) {
    if (l == r) {s[p] ^= 1; return;} //把0改为1，把1改为0，相当于当前数字^1
    int mid (l + r >> 1);
    pos <= mid ? change (ls, l, mid) : change (rs, mid + 1, r);
    s[p] = s[ls] + s[rs];
}
int query (int p, int l, int r) {
    if (ql <= l && qr >= r) return s[p];
    int mid (l + r >> 1), t (0);
    if (ql <= mid) t += query (ls, l, mid);
    if (qr > mid) t += query (rs, mid + 1, r);
    return t;
}
int main() {
    read (n);
    for (int i = 1, u, v; i < n; ++i)
        read (u), read (v), add (u, v), add (v, u);
    dfs (1, 0); build (1, 1, n);
    read (m);
    for (int i = 1; i <= m; ++i) {
        char ch = getchar(); getchar();
        if (ch == 'C') read (pos), pos = num[pos], change (1, 1, n);
        else read (pos), ql = l[pos], qr = r[pos], print (query (1, 1, n)), puts ("");
    }
    return 0;
}