Intersecting Paths

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 spaceseparated integers $N$ and $Q$.  Each of the next $N1$ lines contains two spaceseparated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.  Each of the next $Q$ lines contains two spaceseparated 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)$.Author:  aman_robotics 
Tags  aman_robotics, june19, junechallenge 
Date Added:  30042019 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions