Chef and Gordon Ramsay
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/AUG19/hindi/CHGORAM.pdf), [Bengali](http://www.codechef.com/download/translated/AUG19/bengali/CHGORAM.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/AUG19/mandarin/CHGORAM.pdf), [Russian](http://www.codechef.com/download/translated/AUG19/russian/CHGORAM.pdf), and [Vietnamese](http://www.codechef.com/download/translated/AUG19/vietnamese/CHGORAM.pdf) as well. Chef really admires Gordon Ramsay. Both of them have restaurant chains. While Chef's restaurant chain consists of $N$ facilities (numbered $1$ through $N$), Gordon Ramsay has only $3$, and yet Gordon's restaurants are superior. Chef's marketing team has figured out how to take over the market. According to them, the problem is that the customers have too many restaurants to choose from and that Gordon's staff, by accident or by sheer marketing genius, has figured out the perfect distribution of restaurants. Therefore, Chef wants to close down $N-3$ restaurants as fast as possible and create a restaurant structure similar to Gordon Ramsay's. For that, he needs your help! We know that Gordon Ramsay's restaurants are numbered $1, 2, 3$, where restaurant $1$ is the smallest and restaurant $3$ is the largest. They are located on a line in the order $p_1, p_2, p_3$, so the restaurants $p_1$ and $p_2$ are adjacent and the restaurants $p_2$ and $p_3$ are adjacent too. Chef's restaurant system is a tree with $N$ vertices, where each vertex is one of his precious restaurants. Just like with Gordon's restaurants, they are numbered in the order of increasing size. Chef wants to count the number of ordered triples of restaurants $(a_1, a_2, a_3)$ which he can keep open while satisfying the following rules: 1. The restaurants $a_1$, $a_2$ and $a_3$ are located on a line, i.e. $a_2$ is on the shortest path between $a_1$ and $a_3$ (rebuilding the existing structure would be too costly). 2. For each $i, j$ ($1 \le i, j \le 3$), if $p_i \lt p_j$, then $a_i \lt a_j$. Help Chef and calculate the number of these triples! ### 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 a single integer $N$. - The second line contains three space-separated integers $p_1$, $p_2$ and $p_3$. - Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that the restaurants $u$ and $v$ are connected by an edge. ### Output For each test case, print a single line containing one integer ― the number of triples. ### Constraints - $1 \le T \le 20$ - $3 \le N \le 10^5$ - $1 \le u, v \le N$ - the graph of Chef's restaurants is a tree - the sequence $(p_1, p_2, p_3)$ is a permutation of $(1, 2, 3)$ ### Subtasks **Subtask #1 (5 points):** $1 \le N \le 100$ **Subtask #2 (10 points):** $1 \le N \le 1,000$ **Subtask #3 (10 points):** the tree is a [star graph](http://mathworld.wolfram.com/StarGraph.html) **Subtask #4 (15 points):** the tree is a [path graph](http://mathworld.wolfram.com/PathGraph.html) **Subtask #5 (30 points):** the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$ **Subtask #6 (30 points):** original constraints ### Example Input ``` 1 4 2 1 3 1 2 2 3 2 4 ``` ### Example Output ``` 1 ``` ### Explanation **Example case 1:** The only valid triple is $(3, 2, 4)$.
|Tags||aug19, dfs, euler-tour, fenwick-tree, medium-hard, order-statistic, policy-based-ds, sanroylozan, segment-tree, vijju123|
|Time Limit:||2 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.