Codeforces 375D 子樹顏色統計：四種解法對比

題目大意

給一棵 n (≤10^5) 節點的樹，每節點有顏色。m (≤10^5) 次查詢：詢問以 v 為根的子樹中，出現次數 ≥ k 的顏色有幾種。

四種解法

方法一：莫隊算法（分塊）+ 樹狀數組

• 將查詢離線，按 DFS 序轉化為區間查詢。
• 莫隊算法分塊處理區間增減，維護 cnt[color] 及其頻率桶 freq[x]（有多少顏色出現 x 次）。
• 查詢答案為 sum_{i≥k} freq[i]，用樹狀數組維護後綴和。
• 複雜度 O((n+m)√n log n)。

方法二：莫隊算法優化（O(1) 更新）

• 觀察：增減某顏色計數時，只有 freq[cnt] 和 freq[cnt±1] 變化。
• 直接維護 ans[k] = 出現次數 ≥ k 的顏色數。
  • 加 1：ans[++cnt[c]]++
  • 減 1：ans[cnt[c]--]--
• 無需樹狀數組，更新 O(1)，總複雜度 O((n+m)√n)。

方法三：啟發式合併

• 對每個節點維護其子樹的顏色計數映射（用 map 或 unordered_map）。
• DFS 後序，將小映射合併到大映射中（DSU on tree），複雜度 O(n log^2 n)（map 操作 log）。
• 另維護一個頻率樹（如 Treap）支持後綴和查詢，或直接遍歷大映射統計（若查詢離線按節點分組）。
• 適合動態維護子樹信息場景。

方法四：DSU on Tree（Sack） / 輕重鏈剖分思想

• 對每個節點處理其子樹查詢。遞歸處理輕子樹，計算完清空；重子樹保留不清空。
• 全局數組 cnt[color] 維護當前保留子樹的顏色計數。
• 輕子樹節點加入後即清空，重子樹保留供下層使用。每個節點被加入/刪除次數 ≤ log n。
• 複雜度 O(n log n)，常數極小，是本題最優解法之一。

總結對比

實際比賽中，方法二和方法四是性價比最高的選擇。