Here is a link for some quick explanation.

For example, let's suppose that restaurants must be in increasing order: 1, 2, 3.

Assume that you are checking all the vertexes as the middle one. Now you want to know how many can be the first and how many can be the last, of course, they must belong to different subtrees of our current vertex.

For every vertex i, go through each vertex j that share an edge with i. Try to visualize it as a splitting the tree into two subsets, where subset A is from j to all other vertexes connected to it except from i and subset B the remaining vertexes.

Also, let val be the value of our current vertex. We need to count how many (x, y) pairs we have, where:

• x is in A
• y is in B
• x < val < y

L = how many values are less than val in A

R = how many values are greater than val in B

current_answer = L * R

If the middle value is not 2, after you sum the answer for every vertex, you need to divide the total_answer by two, to remove some repeted pairs.

The biggest problem now is: how to do fast queries on how many values are less/greater than val in a subtree?

I have solved this with persistent segment tree, where I do a query in an interval that represent this subtree. Like:

st[current_version]->query(x, y) - st[current_version - size_of_this_subtree]->query(x, y)

The problem have a tight time limit if you code with persistent segment tree, you can use other faster methods to do this offline, like the small to large trick.