题意分析

题目描述了一棵苹果树，树有N个分叉（节点），编号为1到N，其中1号节点是根节点。每个节点上最多有一个苹果。初始时，所有节点都有苹果。接下来有M个操作，操作分为两种：

1. C x：改变节点x上的苹果状态。如果x有苹果，则摘掉；如果没有，则长出一个。
2. Q x：查询以x为根的子树中苹果的数量（包括x本身）。

解题思路

1. 树的表示：首先需要用合适的数据结构表示这棵树。由于树的节点数可能很大（N ≤ 100,000），我们需要使用邻接表来存储树的结构。
2. 子树查询：为了高效地查询子树中的苹果数量，我们需要对树进行某种遍历，使得子树在遍历序列中是连续的。通常，DFS序或欧拉序可以实现这一点。具体来说，我们可以通过后序遍历或前序遍历为每个节点分配一个进入时间（in）和离开时间（out），这样子树x的节点在序列中的位置就是in[x]到out[x]之间的连续区间。
3. 区间求和：有了DFS序后，子树查询就转化为区间求和问题。单点更新和区间求和可以用树状数组（Fenwick Tree）或线段树（Segment Tree）来实现。由于树状数组实现简单且效率高，通常优先选择。

具体步骤

1. 构建树结构：使用邻接表存储树。
2. DFS遍历：为每个节点分配in和out时间戳。in[x]是第一次访问x的时间，out[x]是遍历完x的子树后离开的时间。子树x的节点在in[x]到out[x]之间。
3. 初始化树状数组：初始时所有节点都有苹果，所以树状数组中每个in[x]的位置初始值为1。
4. 处理操作：
   • C x：改变x的苹果状态。如果x当前有苹果，将树状数组中in[x]位置的值减1；否则加1。
   • Q x：查询区间[in[x], out[x]]的和，即子树x的苹果数量。

标程

import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(stdin.readline())
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)
    
    in_time = [0]*(N+1)
    out_time = [0]*(N+1)
    time = 1
    
    # 使用非递归DFS以避免递归深度问题
    stack = [(1, None, True)]
    while stack:
        u, parent, is_first_visit = stack.pop()
        if is_first_visit:
            in_time[u] = time
            time += 1
            stack.append((u, parent, False))
            # 将子节点按顺序压入栈，这里按原始顺序逆序以保证顺序正确
            for v in reversed(adj[u]):
                if v != parent:
                    stack.append((v, u, True))
        else:
            out_time[u] = time - 1
    
    # 树状数组实现
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(self.size + 2)
        
        def update(self, index, delta):
            while index <= self.size:
                self.tree[index] += delta
                index += index & -index
        
        def query(self, index):
            res = 0
            while index > 0:
                res += self.tree[index]
                index -= index & -index
            return res
        
        def range_query(self, l, r):
            return self.query(r) - self.query(l-1)
    
    ft = FenwickTree(N)
    # 初始化，所有节点都有苹果
    apple = [1]*(N+1)
    for u in range(1, N+1):
        ft.update(in_time[u], 1)
    
    M = int(stdin.readline())
    for _ in range(M):
        parts = stdin.readline().split()
        if parts[0] == 'Q':
            x = int(parts[1])
            l = in_time[x]
            r = out_time[x]
            print(ft.range_query(l, r))
        else:
            x = int(parts[1])
            if apple[x] == 1:
                ft.update(in_time[x], -1)
                apple[x] = 0
            else:
                ft.update(in_time[x], 1)
                apple[x] = 1

if __name__ == '__main__':
    main()

代码解释

1. 输入处理：读取树的边并构建邻接表。
2. DFS遍历：使用非递归DFS（避免递归栈溢出）为每个节点分配in和out时间戳，标记子树在序列中的区间。
3. 树状数组：实现单点更新和区间查询功能。
4. 初始化：初始时所有节点都有苹果，树状数组相应位置初始化为1。
5. 处理操作：
   • Q x：查询子树x的苹果数量，即查询区间[in[x], out[x]]的和。
   • C x：切换节点x的苹果状态，并更新树状数组。

这种方法确保了每次查询和更新操作的时间复杂度为O(log N)，能够高效处理大规模数据。