Codeforces 316 Div2 D Tree Requests：狀態壓縮 + 離線/在線兩種樹上查詢算法

問題抽象

樹上每節點有一個小寫字母。查詢 (v, h)：v 的子樹中深度為 h 的節點字母能否重排成回文串？n,m ≤ 5e5。

回文判定條件

字母頻率中至多一個奇數。用 26 位整數壓縮：第 i 位為 1 表示第 i 個字母出現奇數次。回文 ⇔ (mask & (mask-1)) == 0（即 mask 為 0 或 2 的冪）。

算法一：離線 DFS + 異或前綴和（O(n+m)）

1. 讀入所有查詢，按節點 v 分組存儲 (query_id, h)。
2. DFS 遍歷樹，維護 pre[depth] 為根到當前節點路徑上各深度的字母奇偶掩碼。
3. 進入節點 u 前：對其所有查詢，ans[id] ^= pre[h]（記錄進入前狀態）。
4. 遞歸子樹。
5. 退出節點 u 後：pre[depth] ^= (1 << (char-'a'))（加入當前節點字母）。
6. 再次對查詢 ans[id] ^= pre[h]（記錄退出後狀態）。
7. 兩次異或抵消非子樹部分，ans[id] 即為子樹內深度 h 的字母掩碼。

算法二：在線 DFS 序 + 二分查找（O((n+m) log n)）

1. DFS 記錄每節點進入時間 in[u]、退出時間 out[u]，將子樹轉化為區間 [in[u], out[u]]。
2. 按深度分組，每深度維護有序數組 dep[d] = {(time, mask)}，mask 為該深度從根到當前節點的異或前綴和。
3. 查詢 (v,h)：在 dep[h] 中二分找 in[v] 和 out[v] 的前驅位置 l, r，答案 = dep[h][r].mask ^ dep[h][l].mask。

核心代碼（離線版）

vector<int> tree[N];
vector<pair<int,int>> query[N];
int pre[N], ans[N];
char str[N];

void dfs(int u, int dep) {
    for(auto [id, h] : query[u]) ans[id] ^= pre[h];
    for(int v : tree[u]) dfs(v, dep+1);
    pre[dep] ^= (1 << (str[u-1]-'a'));
    for(auto [id, h] : query[u]) ans[id] ^= pre[h];
}

複雜度對比

離線 O(n+m) 更優，但在線版本思路通用（樹上路徑查詢轉區間查詢），適合強制在線場景。狀態壓縮是關鍵優化，將 26 字母計數壓入單一 int，極大降低內存與時間常數。