問題とコンテキスト
この高難度のコーディング問題は、木の分解、距離の前処理、および動的クエリをテストします。木には n 個の頂点と n-1 個の辺があります。操作はオンラインで届き、初期状態には 1 つの黒頂点があり、トグルは任意です。クエリは木全体を再走査することなく、現在の最近傍黒ノード距離を返す必要があります。
面接官が評価するポイント
- 正しいベースラインから開始し、走査の繰り返しがボトルネックであることを特定できるか。
- すべてのノードが対数長の重心祖先チェーンを持つことを証明し、その距離を維持できるか。
- 成分の除外、重複距離、初期状態の空の黒ノード集合、および整数の境界を適切に処理できるか。
- 重心分解を多始点 BFS、Heavy-Light 分解、および挿入専用バリアントと比較できるか。
確認すべき質問
木が静的であるか、辺の重みが単位長か正の重みか、操作がオンラインか、クエリにノード ID も必要か、操作の並べ替えが許可されているかを確認します。正の辺の重みは重み付き距離を格納することで機能します。辺の更新には別の動的木設計が必要です。
30秒の回答フレームワーク
まずベースラインを提示します：u からの BFS はクエリあたり線形時間です。次に重心分解を構築します。各ノードはすべての重心祖先への距離を格納し、各重心は現在黒であるノードからの最小距離を格納します。クエリは u の重心祖先を辿りながら「u から重心までの距離 ＋ その重心の最善の黒ノード距離」を最小化します。トグルは同じチェーンを更新します。チェーン長は対数であるため、ヒープコストを除けば操作は対数時間であり、前処理は線形対数時間です。
ステップバイステップの詳細な回答
1. ベースラインとボトルネックの確立
u からの BFS は正しいですが、クエリごとにほぼすべての頂点を訪れる可能性があります。トグルが繰り返されると、どの黒頂点が 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 へのパスは、いずれかの分解レベルで共有重心を通過するため、1 つの候補が最適パスを表し、分岐が見落とされることはありません。
4. 重複距離とヒープ削除の処理
2 つのヒープを使用し、有効なヒープに挿入し、削除対象を無効なヒープに記録します。トップを読み取る前に、等しいペアを取り除きます。距離が等しい場合は距離とノード ID の両方を格納する必要があります。そうしないと、あるノードの削除が別のノードを削除してしまう可能性があります。初期黒ノードに対して 1 回の更新を適用し、集合が空の場合は -1 などの文書化された番兵値を返します。
5. 計算量と代替手法
前処理は各分解レベルを走査するため、O(n log n) 時間と O(n log n) の格納リンク数を要します。各操作は対数チェーンを走査しヒープ操作を実行するため、対数のヒープ係数が加わります。ノードが挿入のみの場合は 1 つのヒープでより単純になります。操作が結合的なパス集約である場合はセグメント木を用いた Heavy-Light 分解の方が直接的です。オフライン操作では時間分割統治法を使用できます。
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 を実行する → 正しいがオンラインでは遅すぎる → ベースラインを述べた上で重心チェーンを使用する。
- 最も近い重心のみを更新する → パスがより上位の重心を通過する可能性がある → すべての重心祖先を格納する。
- 距離のみによる遅延削除 → 同じ距離のノードが衝突する → ヒープキーにノード ID を含める。
- 重心分解を LCA として扱う → 解決するタスクが異なる → ノードから動的集合への距離を維持するものとして説明する。
- 空の黒ノード集合の無視 → 未初期化の大きな値を返す →
-1番兵を定義して説明する。
フォローアップの質問と回答
正の辺の重みによってアルゴリズムはどのように変わりますか？
各重心チェーンを収集する際に辺の重みを累積し、重み付き距離をヒープに格納します。分解には依然として成分の頂点数を使用します。非負の重みに対して最小距離の不変条件は変わりません。
クエリが最も近い黒ノードの ID を返す必要がある場合はどうなりますか？
(distance, nodeId) を格納し、辞書式順序で比較します。これにより、距離が同じ場合に決定論的な ID が得られます。クエリは最善の距離と ID の両方を保持します。
u の親重心のみを維持しないのはなぜですか？
最も近い黒ノードが別の部分成分にある場合があり、そのパスはより上位の重心で u と交差します。1 つの親のみを確認すると成分間の最適解を見落とすため、完全な祖先チェーンが必要です。
Heavy-Light 分解が優れているのはどのような場合ですか？
結合的なパス集約、任意の 2 頂点間のパスクエリ、または「1 つの頂点から動的集合への最小距離」ではない黒ノード集合の操作に使用します。重心分解は、各クエリが 1 つの頂点に固定され、変化する集合にわたって集約する場合に最も強みを発揮します。