TREEFUN - Editorial

PROBLEM LINK

Practice
Contest

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

3 Likes

What’s the complexity?

I can’t understand that for k>=3, why we should have T as LCA with the largest height. For example, in tree with 5 vertices and edges as (1,2), (1,3), (2,4), and (2,5) where vertex 1 is root. If query is k=3, and vertex set is (4,5,3). Then LCAs will be X=2, Y=1, Z=1. Here 1 is the vertex with largest height (=2) but it is not a valid vertex while the valid vertex is vertex 2 with height 1. Please clear my doubt.

HEIGHT(V) is the distance from 1 to V. So height of 1 is 0, height of 2 is 1 and the vertex with largest height in your case is 2.

Yes, I also thought that before; but in the pseudo code at last the opposite seems true.