POJ 3321 Apple Tree：樹上 DFS 序 + 線段樹/樹狀數組動態維護子樹和

問題描述

樹上 N≤1e5 個節點，初始每節點有 1 個蘋果。操作：

• C x：翻轉節點 x 蘋果狀態（有→無，無→有）。
• Q x：查詢以 x 為根的子樹內蘋果總數。

DFS 序線性化

• 對樹做 DFS，記錄進入時間 in[x] 和退出時間 out[x]（或 l[x], r[x]）。
• 子樹節點在 DFS 序中構成連續區間 [in[x], out[x]]。
• 問題轉化為：區間翻轉單點值（0/1），區間求和。

樹狀數組實現

單點更新、區間查和。初始所有位置為 1。翻轉時：若當前為 1 則 add(pos, -1)，否則 add(pos, +1)。查詢 sum(r) - sum(l-1)。

代碼

const int MAX = 1e5+5;
int head[MAX], to[MAX*2], nxt[MAX*2], ecnt;
int in[MAX], out[MAX], dfs_clock;
int bit[MAX], val[MAX]; // val 記錄當前狀態

void addEdge(int u,int v){ to[ecnt]=v; nxt[ecnt]=head[u]; head[u]=ecnt++; }
void dfs(int u,int fa){
    in[u]=++dfs_clock;
    for(int i=head[u];~i;i=nxt[i]) if(to[i]!=fa) dfs(to[i],u);
    out[u]=dfs_clock;
}
void bitAdd(int i,int v){ for(;i<=dfs_clock;i+=i&-i) bit[i]+=v; }
int bitSum(int i){ int s=0; for(;i;i-=i&-i) s+=bit[i]; return s; }

int main(){
    int n; while(scanf("%d",&n)==1){
        memset(head,-1,sizeof(head)); ecnt=0;
        for(int i=1;i