Weak Pair

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

You are given a $rooted$ tree of $ N $ nodes, labeled from 1 to $ N $. To the $ i $th node a non-negative value $ a_i $ is assigned.An $ordered$ pair of nodes $ (u, v) $ is said to be $weak$ if
  (1) $ u $ is an ancestor of $ v $ (Note: In this problem a node $ u $ is not considered an ancestor of itself);
  (2) $a_u\times a_v \le k$.

Can you find the number of weak pairs in the tree?

Input

There are multiple cases in the data set.
  The first line of input contains an integer $ T $ denoting number of test cases.
  For each case, the first line contains two space-separated integers, $ N $ and $ k $, respectively.
  The second line contains $ N $ space-separated integers, denoting $ a_1 $ to $ a_N $.
  Each of the subsequent lines contains two space-separated integers defining an edge connecting nodes $u$ and $ v $ , where node $ u $ is the parent of node $ v $.

  Constrains:
  
  $ 1 \le N \le 10^5 $
  
  $ 0 \le a_i \le 10^9 $
  
  $ 0 \le k \le 10^{18} $

Output

For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.

Sample Input

1 2 3 1 2 1 2

Sample Output

1

Hint

wange2014

Source

2016 ACM/ICPC Asia Regional Dalian Online

提交代码