eolymp
bolt
Try our new interface for solving problems
Problems

Mr. Nine and his love for mangoes

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 decides 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. \InputFile The first line consists of integers $n~(1 \le n \le 300005)$, $u$ and $v$. The following $n - 1$ lines consist of two integers $x$ and $y$ denoting there is an edge between vertices $x$ and $y~(1 \le x, y \le n)$. \OutputFile Find out the total number of pair of nodes. \Examples \includegraphics{https://eolympusercontent.com/images/0lo8ib27hp4efegipbvg7j2u54.gif} 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 = 3$ after $u = 1$ and thus it is not acceptable.
Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1 3
1 2
2 3
Output example #1
5