Trees: Depth First Search
Mr. Nine and his love for mangoes
Mr.Nine was roaming casually in the Parralel Universe in his mid-semester breaks, suddenly he comes across a mango tree. He loves mangoes so he decide to pluck some mangoes from it but suddenly a fairy appears and tells him to solve a complex problem to get the mangoes. She tells him that there are n nodes in the trees and he is given two nodes u and v. Now she asks him how many pair of nodes are present in tree in which shortest path between them does not contain node v after node u (for example u -> a -> b -> v is also not allowed where a and b are two different nodes). If he is able to tell the correct number of pair of nodes then he will get all the mangoes,but he is unable to do and needs your help.
The first line consists of integers n (1 ≤ n ≤ 300005), u and v. The following n - 1 lines consist of two space separated integers x and y denoting there is an edge between vertices x and y (1 ≤ x, y ≤ n).
Find out the total number of pair of nodes.
There are 5 possible pairs that can be chosen:
(1, 2) : his route would be 1 → 2
(2, 3) : his route would be 2 → 3
(3, 2) : his route would be 3 → 2
(2, 1) : his route would be 2 → 1
(3, 1) : his route would be 3 → 2 → 1
He cannot choose (1, 3) as a pair because the shortest path between them will be 1 -> 2 -> 3 and this is not acceptable as it contains v after u and thus it is not acceptable.
3 1 3 1 2 2 3