Coding interview: Use centroid decomposition for dynamic nearest-marked-node distance

Prompt and context

This hard coding problem tests tree decomposition, distance preprocessing, and dynamic queries. The tree has n vertices and n-1 edges; operations arrive online, the initial state has one black vertex, and toggles are arbitrary. A query must return the current nearest-black distance without traversing the whole tree again.

What the interviewer evaluates

• Starting with a correct baseline and identifying repeated traversal as the bottleneck.
• Proving that every node has a logarithmic-length centroid-ancestor chain and maintaining its distances.
• Handling component exclusion, duplicate distances, an initially empty black set, and integer bounds.
• Comparing centroid decomposition with multi-source BFS, heavy-light decomposition, and insertion-only variants.

Clarifying questions to ask

Confirm that the tree is static, whether edges are unit or positive weighted, whether operations are online, whether the query also needs a node id, and whether reordering is allowed. Positive edge weights still work by storing weighted distances; edge updates require a different dynamic-tree design.

30-second answer framework

I would first give the baseline: BFS from u is linear per query. Then I build a centroid decomposition. Each node stores its distance to every centroid ancestor, and every centroid stores the minimum distance from a currently black node. A query minimizes “distance from u to centroid plus that centroid’s best black distance” along u’s centroid ancestors; a toggle updates the same chain. The chain is logarithmic, so operations are logarithmic apart from heap costs, with linear-logarithmic preprocessing.

Step-by-step deep answer

1. Establish the baseline and bottleneck

BFS from u is correct, but a query may visit nearly every vertex. After repeated toggles there is no reusable summary of which black vertices are close to u. A global multi-source BFS helps only when the black set changes in batches, not with online flips.

2. Choose centroids and build ancestor chains

Find a centroid of the current connected component so that removing it leaves every component at most half the original size. Recurse on those components to form a centroid tree. An original vertex u has a centroid-ancestor chain; preprocess a pair (centroid, distance) for each link. Component size halves on every level, so the chain length is logarithmic.

3. Maintain update and query invariants

For each centroid c, maintain the minimum dist(v,c) over all currently black vertices v. A min-heap with lazy deletion or a multiset supports this. update(u) inserts or removes dist(u,c) along u’s centroid chain. query(u) minimizes dist(u,c) + best[c] on that chain. Any path from u to a black v passes through their shared centroid at some decomposition level, so one candidate represents the optimal path; no branch is omitted.

4. Handle duplicate distances and heap deletion

With two heaps, insert into the live heap and record deletions in the dead heap; before reading a top, remove equal pairs. Equal distances require storing both distance and node id, otherwise deleting one node can remove another. Apply one update for the initial black node, and return a documented sentinel such as -1 when the set is empty.

5. Complexity and alternatives

Preprocessing traverses each decomposition level, giving O(n log n) time and O(n log n) stored links. Each operation scans a logarithmic chain and performs heap operations, adding a logarithmic heap factor. If nodes are only inserted, one heap is simpler; if the operation is an associative path aggregate, heavy-light decomposition with a segment tree is more direct; offline operations can use time divide-and-conquer.

6. C++ implementation skeleton

The code below uses unit edges, toggles black nodes, and answers nearest-distance queries. Production code can replace recursive traversals with explicit stacks for very deep trees; the recursive form keeps the invariant visible.

#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;}

Model high-quality answer

I would turn the static tree into a centroid tree. During preprocessing, each vertex records its distance to every centroid ancestor; each centroid stores the minimum distance from a current black vertex. A toggle inserts or lazily removes the distance along that ancestor chain. A query minimizes the distance to each centroid plus that centroid’s best black distance. Every path meets its shared centroid at some level, so the optimal black vertex is represented. The centroid chain is logarithmic, giving O(n log n) preprocessing and logarithmic-chain operations, multiplied by heap costs. With insertions only I would remove the deletion heap; with changing edges I would choose a dynamic-tree structure.

Common mistakes

• BFS for every query → correct but too slow online → state the baseline, then use the centroid chain.
• Updating only the nearest centroid → a path can cross a higher centroid → store every centroid ancestor.
• Lazy deletion by distance alone → equal-distance nodes collide → include the node id in the heap key.
• Treating centroid decomposition as LCA → they solve different tasks → state that this maintains distance from a node to a dynamic set.
• Ignoring an empty black set → returns an uninitialized large value → define and explain a -1 sentinel.

Follow-up questions and responses

How do positive edge weights change the algorithm?

Accumulate edge weights while collecting each centroid chain and store weighted distances in the heaps. Decomposition still uses component vertex counts; the minimum-distance invariant is unchanged for nonnegative weights.

What if the query must return the nearest black node id?

Store (distance, nodeId) and compare lexicographically. This gives a deterministic id when distances tie; the query carries both the best distance and id.

Why not maintain only u’s parent centroid?

The nearest black node may lie in a different child component, with the path meeting u at a higher centroid. Checking one parent misses cross-component optima, so the full ancestor chain is required.

When is heavy-light decomposition better?

Use it for associative path aggregates, arbitrary two-vertex path queries, or a black-set operation that is not “minimum distance from one vertex to a dynamic set.” Centroid decomposition is strongest when every query is anchored at one vertex and aggregates over a changing set.