題幹與適用場景
這是進階程式題，考察樹分解、距離預處理與動態查詢。樹有 n 個節點與 n-1 條邊，操作在線上到達；初始只有一個節點為黑色，之後可任意翻轉。查詢必須回傳目前最近黑點距離，不能每次重新遍歷整棵樹。
面試官考察什麼
- 能否先給出樸素基線，再識別重複遍歷的瓶頸。
- 能否證明每個節點到重心祖先鏈的長度是對數級，並正確維護鏈上距離。
- 能否處理重心分解的子樹排除、重複計數、初始無黑點與整數上界。
- 能否比較點分治與多源 BFS、重鏈剖分、固定黑點場景的適用條件。
回答前需要釐清的問題
需要確認樹是否靜態、邊權是否全為一、操作是否在線上、查詢是否只要最小距離還要回傳節點編號，以及是否允許離線重排。若邊權為正數，點分治仍可用但距離改為加權和；若樹會改邊，靜態分解不再直接適用。
30 秒回答框架
我會先說明樸素方案每次從 u 做 BFS，最壞會是線性。然後對樹做點分治：每個節點保存它到所有祖先重心的距離；每個重心維護黑點到自己的最小距離。查詢沿 u 的重心祖先鏈取「u 到重心距離加該重心最小黑點距離」的最小值，更新只需沿同一條鏈更新堆或集合。重心鏈長是對數級，所以每次操作為對數級，預處理為線性對數級。
分步驟深入解答
1. 建立樸素基線與瓶頸
每次 query 從 u 做 BFS 可以得到正確答案，但一次查詢會造訪大量節點；反覆 update 後無法重用「哪些黑點離 u 近」的結構。全域多源 BFS 只適合黑點批次變化，不適合線上翻轉。
2. 選擇重心並建立祖先鏈
在目前連通分量中找重心，使刪除它後每個子分量規模不超過原分量的一半。遞迴處理各子分量，形成一棵重心樹。原樹節點 u 在重心樹上有一條祖先鏈；預處理每個鏈節點對 (centroid, distance)。每層規模至少減半，因此鏈長不超過對數級。
3. 維護更新與查詢不變量
對每個重心 c，維護所有目前黑節點 v 的 dist(v,c) 最小值。可以用最小堆加惰性刪除，或用 multiset 支援插入與刪除。update(u) 沿 u 的重心祖先鏈，把 dist(u,c) 加入或刪除。query(u) 對同一條鏈計算 dist(u,c) + best[c] 的最小值。任意路徑 u 到黑點 v 會在某一層經過共同重心，因此這個組合涵蓋最優路徑；每個重心只負責候選，不會漏解。
4. 處理重複計數與堆刪除
若使用兩個堆，加入操作寫入 live 堆，刪除操作寫入 dead 堆；讀取堆頂前持續彈出兩堆相等的值。若邊權可能相同，堆中應存距離和節點編號，按二元組惰性刪除，避免只比較距離造成誤刪。初始黑點應先執行一次 update，查詢無黑點時回傳約定的無窮大。
5. 複雜度與替代方案
點分治預處理需要遍歷每層分量，總複雜度為 O(n log n)，空間為 O(n log n)；每次 update 與 query 造訪對數條鏈，堆操作再乘一個對數因子。若黑點只增加不刪除，可用單堆且實作更簡單；若查詢是固定路徑聚合，重鏈剖分和線段樹更自然；若所有操作離線，可考慮按時間分治。
6. C++ 實作骨架
下面程式碼展示單位邊權、黑點翻轉和最短距離查詢。為避免遞迴堆疊過深，生產實作可把找重心的遍歷改成顯式堆疊；示例保留遞迴結構以突出不變量。
#include <bits/stdc++.h>
using namespace std;
struct Entry { int d, u; bool operator>(const Entry& o) const { return tie(d,u) > tie(o.d,o.u); } };
int n; vector<vector<int>> g; vector<int> sub, dead, black;
vector<vector<pair<int,int>>> chain;
vector<priority_queue<Entry, vector<Entry>, greater<Entry>>> liveHeap, deadHeap;
void calcSize(int u, int p) { sub[u]=1; for (int v:g[u]) if(v!=p&&!dead[v]){calcSize(v,u);sub[u]+=sub[v];} }
int findCentroid(int u,int p,int total){ for(int v:g[u]) if(v!=p&&!dead[v]&&sub[v]>total/2)return findCentroid(v,u,total); return u; }
void collect(int u,int p,int c,int d){ chain[u].push_back({c,d}); for(int v:g[u]) if(v!=p&&!dead[v])collect(v,u,c,d+1); }
void decompose(int entry){ calcSize(entry,-1); int c=findCentroid(entry,-1,sub[entry]); dead[c]=1; collect(c,-1,c,0); for(int v:g[c]) if(!dead[v])decompose(v); }
void clean(int c){ while(!liveHeap[c].empty()&&!deadHeap[c].empty()&&liveHeap[c].top().d==deadHeap[c].top().d&&liveHeap[c].top().u==deadHeap[c].top().u){liveHeap[c].pop();deadHeap[c].pop();} }
void update(int u){ black[u]^=1; for(auto [c,d]:chain[u]){ if(black[u])liveHeap[c].push({d,u}); else deadHeap[c].push({d,u}); } }
int query(int u){ const int INF=1e9; int ans=INF; for(auto [c,d]:chain[u]){clean(c);if(!liveHeap[c].empty())ans=min(ans,d+liveHeap[c].top().d);} return ans==INF?-1:ans; }高品質示範回答
我會用點分治把靜態樹變成重心樹。預處理時，為每個節點記錄到每個重心祖先的距離；每個重心維護目前黑點到它的最小距離。翻轉節點時沿祖先鏈插入或惰性刪除距離，查詢時取所有祖先的「到重心距離加重心最小黑點距離」的最小值。路徑在某層一定經過共同重心，所以最優黑點不會漏掉。重心鏈是對數長度，預處理約為 O(n log n)；使用堆惰性刪除時更新和查詢為對數鏈長乘堆操作開銷。若只有新增沒有刪除，我會移除刪除堆；若樹邊會動態改變，則改用支援動態樹的結構。
常見錯誤
- 每次查詢 BFS → 正確但無法承受大量線上操作 → 先給基線，再引入重心鏈。
- 只把節點加入最近重心 → 路徑可能經過更高層重心 → 為每個節點保存完整祖先鏈。
- 惰性刪除只比較距離 → 相同距離的不同節點會誤刪 → 堆項同時記錄節點編號。
- 把重心分解誤當成 LCA → 兩者解決的問題不同 → 明確這裡維護的是動態集合到單點距離。
- 忽略初始無黑點 → 回傳未初始化的大數 → 約定回傳
-1並在框架中說清楚。
追問及應對
如果邊有正權，演算法要怎麼改？
收集祖先鏈時累計邊權而非步數，堆裡保存加權距離；重心分解依據節點數仍成立。若允許零或正權，最小值不變量不變。
如果還要回傳最近黑點的編號呢？
堆項保存 (distance, nodeId) 並按字典序比較。多個黑點同距時可按編號穩定選取；查詢組合時同時維護目前最優距離和編號。
為什麼不能只維護 u 的父重心？
最近黑點可能位於與 u 不同的子分量，路徑會在更高層重心匯合。只檢查一個父重心會漏掉跨分量的最優答案，必須遍歷整條祖先鏈。
什麼時候重鏈剖分更合適？
當操作是路徑上的可結合聚合、需要查詢任意兩點路徑，或黑點集合不是「節點到集合的最小距離」時，重鏈剖分加線段樹通常更直接。點分治適合圍繞一個節點對動態集合做距離聚合。