BlackandWhite Tree

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK112/hindi/BLWHTREE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK112/mandarin/BLWHTREE.pdf), [Russian](http://www.codechef.com/download/translated/COOK112/russian/BLWHTREE.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK112/vietnamese/BLWHTREE.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK112/bengali/BLWHTREE.pdf) as well. Chefland is a country with $N$ cities (numbered $1$ through $N$) connected by $N1$ bidirectional roads. It is possible to travel from each city to any other city using the roads. Moreover, each city is specialised in either black or white chocolate. Chef wants to construct three new restaurants. However, he is still not sure where to build them. You should answer $Q$ queries; in each query, Chef gives you two cities $L$ and $R$ and you should find the number of ways to choose a set of three distinct cities that satisfies the following conditions:  The chosen cities belong to the shortest path between the cities $L$ and $R$ (both inclusive).  For any two chosen cities (let's denote them by $u$ and $v$; $u \neq v$), there is at least one city specialised in black chocolate on the shortest path between the cities $u$ and $v$ (both inclusive). ### 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 $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$. For each valid $i$, $A_i = 1$ if the $i$th city is specialised in black chocolate or $0$ if it is specialised in white chocolate.  Each of the following $N1$ lines contains two spaceseparated integers $x$ and $y$ denoting that cities $x$ and $y$ are connected by a road.  The next line contains a single integer $Q$.  Each of the following $Q$ lines contains two spaceseparated integers $L$ and $R$ describing a query. ### Output For each query, print a single line containing one integer — the number of ways to choose three cities. ### Constraints  $1 \le T \le 5$  $1 \le N, Q \le 10^5$  $0 \le A_i \le 1$ for each valid $i$  $1 \le x, y \le N$  $1 \le L, R \le N$ ### Example Input ``` 1 12 1 1 0 0 1 0 1 1 0 1 1 1 1 10 5 1 7 6 6 12 4 6 1 6 2 6 11 1 3 1 1 9 8 1 9 8 4 2 9 3 8 6 12 2 9 1 9 7 12 1 5 10 6 ``` ### Example Output ``` 2 4 1 0 4 0 1 0 1 ```Author:  dalgerok 
Tags  dalgerok 
Date Added:  4112019 
Time Limit:  3 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, SQL, 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
HELP
If you are still having problems, see a sample solution here. 