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 $N-1$ 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$ space-separated 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 $N-1$ lines contains two space-separated 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 space-separated 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 ```
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.