Max Distance to Marked Vertices

The Problem

You have a tree with \(n\) vertices. Some vertices are marked. For each vertex \(i\), define \(f_i\) = maximum distance from \(i\) to any marked vertex.

Find the vertex that minimizes \(f_i\). In other words: where should you stand to be as close as possible to the farthest marked vertex?

Constraints: \(n \leq 2 \times 10^5\).

This appears on Codeforces and CSES. It tests whether you understand the structure of distances on trees.

The Naive Approach

For each vertex, BFS to find the distance to every marked vertex, take the max. Then pick the vertex with the smallest max.

Time: \(O(n^2)\) — one BFS per vertex. Too slow for \(n = 2 \times 10^5\).

The Key Insight: The Diameter of the Marked Set

The maximum distance from any vertex to the marked set is determined by at most two marked vertices — the endpoints of the "marked diameter."

Here's why. Consider all marked vertices. The marked diameter is the longest path between any two marked vertices. Call its endpoints \(A\) and \(B\).

For any vertex \(v\), the farthest marked vertex from \(v\) is either \(A\) or \(B\) (or occasionally tied with another marked vertex on the diameter path). This is a property of trees: distances are determined by paths, and the longest path dominates.

So: \(f_v = \max(\text{dist}(v, A),\; \text{dist}(v, B))\).

The Algorithm: Two BFS

Find endpoint \(A\): BFS from any marked vertex. The farthest marked vertex from it is \(A\).
Find endpoint \(B\): BFS from \(A\). The farthest marked vertex from \(A\) is \(B\).
Compute distances: BFS from \(A\) gives distA[]. BFS from \(B\) gives distB[].
Answer: For each vertex \(v\), \(f_v = \max(\texttt{distA}[v],\; \texttt{distB}[v])\). The answer is \(\min_v f_v\).

Total: 3 BFS passes = \(O(n)\).

Full Trace

Tree (7 nodes):

Marked vertices: {4, 5, 7}.

Step 1: BFS from any marked vertex (say, vertex 4).

Node	dist from 4
4	0
2	1
1	2
5	2
3	3
6	4
7	5

Farthest marked vertex from 4: vertex 7 (distance 5). So \(A = 7\).

Step 2: BFS from \(A = 7\).

Node	distA (from 7)
7	0
6	1
3	2
1	3
2	4
4	5
5	5

Farthest marked vertex from 7: vertex 4 or 5 (distance 5). So \(B = 4\).

Step 3: BFS from \(B = 4\).

Node	distB (from 4)
4	0
2	1
1	2
5	2
3	3
6	4
7	5

Step 4: Compute \(f_v = \max(\texttt{distA}[v], \texttt{distB}[v])\) for each vertex.

Node	distA (from 7)	distB (from 4)	\(f_v\) = max
1	3	2	3
2	4	1	4
3	2	3	3
4	5	0	5
5	5	2	5
6	1	4	4
7	0	5	5

Minimum \(f_v\): Vertices 1 and 3 both have \(f_v = 3\). Answer: 3.

Verification: From vertex 1, the farthest marked vertex is 7 (distance 3). From vertex 3, the farthest is 4 (distance 3). Both are correct — standing at vertex 1 or 3 minimizes the maximum distance to any marked vertex.

Why Two Endpoints Suffice

On a tree, for any vertex \(v\), the farthest point in a set \(S\) must be one of the two endpoints of the diameter of \(S\). This follows from the tree metric property: all distances go through unique paths, and the diameter endpoints maximize reach in opposite directions.

Formally: if \(A\) and \(B\) are the diameter endpoints of the marked set, then for any marked vertex \(m\) and any vertex \(v\):

\[\text{dist}(v, m) \leq \max(\text{dist}(v, A),\; \text{dist}(v, B))\]

This is because \(m\) lies on or "between" the diameter path, so it's never farther from \(v\) than both endpoints.

The Code

int nodeCount;
cin >> nodeCount;
vector<vector<int>> adj(nodeCount + 1);
for (int i = 0; i < nodeCount - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int markedCount;
cin >> markedCount;
vector<int> marked(markedCount);
vector<bool> isMarked(nodeCount + 1, false);
for (auto& m : marked) {
    cin >> m;
    isMarked[m] = true;
}

auto bfs = [&](int source) -> vector<int> {
    vector<int> dist(nodeCount + 1, -1);
    queue<int> bfsQueue;
    dist[source] = 0;
    bfsQueue.push(source);
    while (!bfsQueue.empty()) {
        int u = bfsQueue.front();
        bfsQueue.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                bfsQueue.push(v);
            }
    }
    return dist;
};

auto farthestMarked = [&](vector<int>& dist) -> int {
    int best = marked[0];
    for (int m : marked)
        if (dist[m] > dist[best])
            best = m;
    return best;
};

vector<int> distFromAny = bfs(marked[0]);
int endpointA = farthestMarked(distFromAny);

vector<int> distA = bfs(endpointA);
int endpointB = farthestMarked(distA);

vector<int> distB = bfs(endpointB);

int bestVertex = 1;
int bestMaxDist = nodeCount;
for (int v = 1; v <= nodeCount; v++) {
    int maxDist = max(distA[v], distB[v]);
    if (maxDist < bestMaxDist) {
        bestMaxDist = maxDist;
        bestVertex = v;
    }
}

cout << bestMaxDist << "\n";

Complexity: \(O(n)\) time (3 BFS passes), \(O(n)\) space.

Variants

Variant 1: Find \(f_v\) for ALL vertices — already computed. Output max(distA[v], distB[v]) for each \(v\).

Variant 2: Only marked vertices can be chosen — restrict the final loop to marked vertices only.

Variant 3: Weighted edges — replace BFS with Dijkstra or DFS with edge weights. The diameter-endpoint property still holds on weighted trees.

Variant 4: Find the optimal point on an edge (not just vertex) — the optimal point is on the path between \(A\) and \(B\), at distance \(\lceil d(A,B)/2 \rceil\) from the closer endpoint.

Edge Cases to Watch For

Single marked vertex: \(A = B\) = that vertex. \(f_v = \text{dist}(v, A)\) for all \(v\). The answer is 0 (stand on the marked vertex).
All vertices marked: The answer is \(\lceil \text{diameter} / 2 \rceil\) — the tree's center.
Marked set forms a path: The answer is the midpoint of that path.

Problems

Problem	Link	Difficulty
CF 1822F — Gardening Friends	codeforces.com/contest/1822/problem/F	Medium
CSES — Tree Distances I	cses.fi/problemset/task/1132	Medium
CF 337D — Book of Evil	codeforces.com/contest/337/problem/D	Hard
CF 519E — A and B and Lecture Rooms	codeforces.com/problemset/problem/519/E	Hard
CF 609E — MST for Each Edge	codeforces.com/problemset/problem/609/E	Hard