HDU 3887 Counting Offspring：DFS 序 + BIT 求子樹權值和

問題重述

給定一棵根為 p 的樹，節點編號 1..n。定義 f(i) = 節點 i 的子樹中編號 **小於 i** 的節點數。求所有 f(i)。

DFS 序映射子樹為區間

DFS 遍歷記錄進入時間 L[u]、退出時間 R[u]。子樹 u 對應區間 [L[u], R[u]]（或 [L[u], L[u]+sz[u]-1]）。

離線處理：從大到小插入

因為只統計「編號小於 i」的節點，我們按節點編號 **從 n 遞減到 1** 處理：
1. 查詢區間 [L[i], R[i]] 內已插入的節點數（這些節點編號均 > i）。
2. 將當前節點 i 插入 BIT（在位置 L[i] 加 1）。
3. 答案 = 查詢結果。

BIT 實現細節

int query(int x) { int s=0; for(;x;x-=x&-x) s+=c[x]; return s; }
void add(int x, int v) { for(;x<=n;x+=x&-x) c[x]+=v; }

// 主循環
for (int i = n; i >= 1; --i) {
    ans[i] = query(R[i]) - query(L[i]-1);
    add(L[i], 1);
}

遞歸棧溢出解決方案

n ≤ 1e5，遞歸 DFS 可能爆棧。三種應對：
1. #pragma comment(linker, "/STACK:1024000000")（MSVC）。
2. 手寫棧模擬 DFS。
3. 增加編譯選項 -Wl,--stack=268435456（GCC/MinGW）。

複雜度

DFS O(N)，BIT 操作 O(N log N)，總 O(N log N)，空間 O(N)。