# PROBLEM LINK

# DIFFICULTY

MEDIUM - HARD

# PREREQUISITES

Graph Theory, Lowest Common Ancestor

# PROBLEM

You are given a Tree on N nodes. You have to answer several queries of the following kind

- Given K vertices { V
_{1}, V_{2}…, V_{K}} - Find the number of vertices, outside the set of K vertices, that you can remove, such that
- The K vertices are disconnected.
- This means that if you pick any two vertices V
_{i}and V_{j}, they should belong to two separate connected components.

# QUICK EXPLANATION

First, root the tree on vertex with label 1.

This means, for each vertex, set the parent such that you have a directed tree, whose root is 1.

Precompute ancestors for finding LCA (lowest common ancestor) for any pair of vertices. (Expected complexity O(N log N))

Then, for each query you can compute the answer as below

- K = 2, The answer is the number of vertices in the unique path from V
_{1}to V_{2} - K ≥ 3, The answer will be either 1 or 0. It will be 1 iff there is a vertex that can be removed to achieve the goal.

# EXPLANATION

## K = 2

Let L = LCA(V_{1}, V_{2})

The answer will be

**HEIGHT(V _{1}) - HEIGHT(L) + HEIGHT(V_{2}) - HEIGHT(L) - 1**

This value is equal to the number of vertices on the path from V_{1} to V_{2}. Since, removing any vertex from this path will result in disconnecting the two vertices.

## K ≥ 3

First, let us prove that the answer will always be 1 or 0.

We call a vertex whose removal causes the K vertices to be disconnected, a valid vertex.

**Theorem**: There will be unique non intersecting paths from a valid vertex V to each of the K vertices.

**Proof**:

Assume that the path from V to V_{i}, { V, P_{1}, P_{2} …, V_{i} }, intersects with the path from V to V_{j}, { V, Q_{1}, Q_{2} …, V_{j} }.

Since these are vertices of a Tree, the paths can only intersect if

P_{1} = Q_{1}

But, if P_{1} = Q_{1}, then V_{i} and V_{j}, will still be connected by a path { V_{i} …, P_{2}, P_{1}, Q_{2} …, V_{j} }

Hence, either V is not a valid vertex, or V has non intersecting paths to each of the K vertices. QED

**Theorem**: There will be at most 1 valid vertex.

**Proof**:

Assume there are two valid vertices P_{1} and P_{2}.

This means that there are non-intersecting paths from P_{1} to each of the K vertices AND from P_{2} to each of the K vertices.

But, in this case, for some V_{i} and V_{j}, we will get a cycle P_{1} => V_{i} => P_{2} => V_{j} => P_{1}

This contradicts the **axiom** that there are no cycles in the tree.

Hence, either the graph is not a tree, or there is only 1 valid vertex. QED

Now, the valid vertex has to be one of the vertices below

X = LCA(V_{1}, V_{2})

Y = LCA(V_{2}, V_{3})

Z = LCA(V_{3}, V_{1})

In fact, it is easy to see that it will be that vertex, whose HEIGHT is largest!

**(The proof is left as an exercise to the reader)**

Thus, find the vertex T from { X, Y, Z } such that its height is largest.

If T = V_{1} OR V_{2} OR V_{3} then the answer is 0.

Otherwise,

For this vertex, maintain a set of neighbour vertices which have been used in a unique path from T to some vertex in K.

init set of neighbours used S = {} for each vertex v in K find the neighbour of T which falls on the path from T to v This neighbour will either be the parent of T, or immediate child if HEIGHT(v) < HEIGHT(T) then find n = Ancestor(v, HEIGHT(T) - HEIGHT(v) - 1) if parent[n] = T, S.put(n) else S.put(parent[T])

If there are K vertices in S, then there are K non-intersecting paths from T to each of the K vertices. The answer is 1.

Otherwise, the answer is 0.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here