Codeforces Round #294 Div. 2 Problem E - A and B and Lecture Rooms

Problem Statement:
519E - A and B and Lecture Rooms

Solution:
A very innocent looking problem, but really we shouldn't judge a book by its cover :P. Very difficult to solve as it requires a lot of data structures to implement, and several problems are layered very nicely together. Let's see what I mean.

First of all, we know that we are dealing with a tree. Between to rooms x and y, we know that there will only exist one and unique simple path between them (otherwise if there exist two paths, then there exist a cycle in the tree, a contradiction).