All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JUNE19/hindi/INTRPATH.pdf), [Bengali](http://www.codechef.com/download/translated/JUNE19/bengali/INTRPATH.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JUNE19/mandarin/INTRPATH.pdf), [Russian](http://www.codechef.com/download/translated/JUNE19/russian/INTRPATH.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JUNE19/vietnamese/INTRPATH.pdf) as well. You are given a tree (a connected undirected graph without cycles) with $N$ vertices numbered $1$ through $N$. For each pair of vertices $u$ and $v$, let's denote the simple path between them by $(u, v)$; the paths are undirected, so $(u, v)$ is the same path as $(v, u)$. You should answer $Q$ queries. In each query, you are given two vertices $u$ and $v$. Then, for each simple path $(a, b)$ in the tree, we define *perfect intersection* as follows: - Let's denote the sets of vertices in the paths $(u, v)$ and $(a, b)$ by $S_1$ and $S_2$ respectively (a path contains its endpoints too). - The path $(a, b)$ intersects perfectly with $(u, v)$ if $|S_1 \cap S_2| = 1$, i.e. these paths have exactly one common vertex. The answer to the query is the number of paths which intersect perfectly with the path $(u, v)$. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $Q$. - Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge. - Each of the next $Q$ lines contains two space-separated integers $u$ and $v$ describing one query. ### Output For each query, print a single line containing one integer — the answer to this query. ### Constraints - $1 \le T \le 10$ - $1 \le N, Q \le 3 \cdot 10^5$ - $1 \le u, v \le N$ ### Subtasks **Subtask #1 (10 points):** $1 \le N, Q \le 100$ **Subtask #2 (20 points):** $1 \le N, Q \le 1,000$ **Subtask #3 (70 points):** - $T \le 5$ - $1 \le N \le 250,000$ - $1 \le Q \le 3 \cdot 10^5$ ### Example Input ``` 1 6 2 1 2 1 3 1 4 2 5 2 6 4 5 1 3 ``` ### Example Output ``` 6 9 ``` ### Explanation **Example case 1:** In the first query, the paths that intersect perfectly with the given path $(4, 5)$ are $(1, 1)$, $(1, 3)$, $(2, 2)$, $(2, 6)$, $(4, 4)$ and $(5, 5)$.
|Tags||aman_robotics, june19, junechallenge|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.