Chef and Math Test

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Joud Zouzou is one of the new employed cochefs in the restaurant.
Joud is preparing for his 3^{rd} year in Damascus University, and he is also an ACM (ACMilan) fan. Said On the other hand is a fan of Juventus, and they always fight, especially when Joud says: We're coming, We're back!
Said can't stand this situation, but Shahhoud decided to give Joud his last chance. Since his dream is to be the Chef that cooks the most delicious dishes, Shahhoud gave him a task, and Joud has to solve it in order to maintain his current job. The task is as follows
Given a tree of N nodes, each node i has a value A_{i} attached to it. Joud has to find the number of unorderedpairs (i,j) such that:
If we created an array of all the numbers A_{k}, such as k is a node in the simple path from node i to node j, the median of this array will not exceed X and the mean will be at least Y.
Joud found this task a bit hard, and he wants to spend all of his time studying for the next year, so he asked you to help him solving that problem.
Note:
 The median of an array is the element positioned at the middle of the array after sorting it in nondecreasing order.
 The mean of an array is the sum of all the elements, divided by array's length.
 You can consider for evenlength arrays that the median is the left one of the two centered elements of the array after sorting it.
Input
The first line of the input contains an integer T denoting the number of test cases.
Each test starts with three space separated integers N, X and Y, denoting the number of nodes, the maximum value for the median and the minimum value for the mean respectively.
The next line contains N space separated integers A_{1}, A_{2}, ..., A_{N}, denoting the values of the nodes.
N1 lines follows. Each line contains two values: u and v, denoting a connection between nodes u and v.
Output
For each test case, print a single number, the number of pairs (u, v) that satisfies the above mentioned conditions. It's possible that u = v.
Constraints
 1 ≤ T ≤ 100.
 1 ≤ N ≤ 10^{5}.
 10^{9} ≤ X,Y ≤ 10^{9}.
 10^{9} ≤ A_{i} ≤ 10^{9}.
 It's guaranteed that the sum of all N over all test cases doesn't exceed 2*10^{5}.
Example
Input: 1 5 4 0 1 5 4 6 100 4 2 2 1 5 3 1 3 Output: 7
Explanation
Example case 1: All possible pairs are: { (1,1) (1,2) (1,3) (1,4) (1,5) (2,2) (2,3) (2,4) (2,5) (3,3) (3,4) (3,5) (4,4) (4,5) (5,5) }. The valid pairs are: { (1,1) (1,2) (1,3) (1,4) (2,3) (3,3) (3,4) }.
The pair (1,5) is invalid because if we get all the nodes values in the path from node 1 to node 5, the array will be: {1, 4, 100}, and the mean is: 31,666 which is less than 0.
The pair (2,2) is invalid because the median of the array {5} is 5 which is greater than 4
Author:  saeed_sryhini 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/CK87MEAD 
Tags  centroiddecomp, cook87, fenwicktree, linesweep, mediumhard, mhammad1, saeed_sryhini 
Date Added:  20102017 
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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions