#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/E

Repovive

Repovive.

Back

Code

Upload

Submissions

3E. Distant Friends

2500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Rayan discovered $n$ ancient temples connected by mystical pathways. The temples and pathways form a tree, meaning there is exactly one path between any two temples.

Each temple $i$ has a power level $p_i$ , and each pathway has a length $w$ .

For two temples $u$ and $v$ , let $d(u, v)$ denote the sum of pathway lengths on the unique path between them.

Two temples are distant friends if the path length between them is at least $D$ .

For each temple $u$ , compute its contribution: $p_u \times (\text{number of distant friends of } u)$

Find the sum of contributions over all temples.

Constraints

$1 \le t \le 1000$
$1 \le n \le 10^5$
$0 \le D \le 10^9$
$0 \le p_i \le 10^6$
$1 \le u, v \le n$
$1 \le w \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \quad D \\ p_1 \quad p_2 \quad \cdots \quad p_n \\ u_1 \quad v_1 \quad w_1 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad w_{n-1} \end{array} \right\} \times t

Output

\begin{array}{l} ans_1 \\ \vdots \\ ans_t \end{array}

Samples

Input

Explanation

Input: n=3, D=3, powers=[2,3,1]

Tree edges: 1-2 (weight 3), 2-3 (weight 4)

Find sum of power products for pairs with distance ≥ D.

Answer: 12

Output

Input

1
1 0
5

Explanation

Input: n=1, D=0, powers=[5]

Single node, no pairs.

Answer: 0

Output

Input

Explanation

Input: 5 test cases with various tree configurations.

Answer: 12 0 0 30 12

Output

Rayan discovered $n$ ancient temples connected by mystical pathways. The temples and pathways form a tree, meaning there is exactly one path between any two temples.

Each temple $i$ has a power level $p_i$ , and each pathway has a length $w$ .

For two temples $u$ and $v$ , let $d(u, v)$ denote the sum of pathway lengths on the unique path between them.

Two temples are distant friends if the path length between them is at least $D$ .

For each temple $u$ , compute its contribution: $p_u \times (\text{number of distant friends of } u)$

Find the sum of contributions over all temples.

Constraints

$1 \le t \le 1000$
$1 \le n \le 10^5$
$0 \le D \le 10^9$
$0 \le p_i \le 10^6$
$1 \le u, v \le n$
$1 \le w \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \quad D \\ p_1 \quad p_2 \quad \cdots \quad p_n \\ u_1 \quad v_1 \quad w_1 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad w_{n-1} \end{array} \right\} \times t

\begin{array}{l} ans_1 \\ \vdots \\ ans_t \end{array}