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 { V1, V2 …, VK }
- 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 Vi and Vj, 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 V1 to V2
- 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(V1, V2)
The answer will be
HEIGHT(V1) - HEIGHT(L) + HEIGHT(V2) - HEIGHT(L) - 1
This value is equal to the number of vertices on the path from V1 to V2. 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 Vi, { V, P1, P2 …, Vi }, intersects with the path from V to Vj, { V, Q1, Q2 …, Vj }.
Since these are vertices of a Tree, the paths can only intersect if
P1 = Q1
But, if P1 = Q1, then Vi and Vj, will still be connected by a path { Vi …, P2, P1, Q2 …, Vj }
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 P1 and P2.
This means that there are non-intersecting paths from P1 to each of the K vertices AND from P2 to each of the K vertices.
But, in this case, for some Vi and Vj, we will get a cycle P1 => Vi => P2 => Vj => P1
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(V1, V2)
Y = LCA(V2, V3)
Z = LCA(V3, V1)
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 = V1 OR V2 OR V3 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