34634번 - Victorious Coloring (Hard Version) 다국어

문제

This is the hard version of the problem. The difference between the versions is that in this version, $q \le 250,000円$. You can hack only if you solved all versions of this problem.

You are given a tree with $n$ vertices, where each vertex is numbered from 1ドル$ to $n$. Each edge is assigned a positive integer weight $w_1, w_2, \ldots, w_{n-1}$ as well.

A victorious coloring is a coloring of each vertex into two colors: red and yellow, where there should be at least one vertex colored in red (corresponding to the symbol of team T1).

Suppose that there is a nonnegative integer weight $x_1, x_2, \ldots, x_n$ assigned to each vertex. The cost of the victorious coloring is defined as the sum of the weights of all red vertices, plus the sum of the weights of all edges that connect vertices of different colors (between red and yellow). We define $f([x_1, x_2, \ldots, x_n])$ as the minimum possible cost for all victorious colorings.

Gumayusi considered the problem of computing $f([x_1, x_2, \ldots, x_n]),ドル given the sequence $x_1, x_2, \ldots, x_n$. However, this problem was too easy for him, so he devised a variation: Given an integer $l,ドル find a sequence of nonnegative integer vertex weights $[x_1, x_2, \ldots, x_n]$ such that $f([x_1, x_2, \ldots, x_n]) \ge l$ and the total sum $\sum_{i=1}^n x_i$ is minimized.

Gumayusi was satisfied, but there was a serious issue --- this problem doesn't have any queries, which is a necessary component for any problem that isn't bad. So, he added queries to this problem. For each $l$ given as a query, you must find the corresponding minimum possible sum of vertex weights.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 10^4$). The description of the test cases follows.

The first line contains an integer $n$ (2ドル \le n \le 250,000円$) --- the number of vertices.

The following $n-1$ lines contain three integers $u_i,ドル $v_i,ドル $w_i$ (1ドル \le u_i, v_i \leq n, 1 \le w_i \le 10^9, u_i \neq v_i$) --- indicating an edge connecting the vertices $u_i$ and $v_i$ with weight $w_i$.

It is guaranteed that the edges form a tree.

The next line contains an integer $q$ (1ドル \le q \le 250,000円$) --- the number of queries.

The following $q$ lines contain a single integer $l_i$ (1ドル \leq l_i \leq 10^9$) --- the parameters of the $i$-th query.

It is guaranteed that the sum of $n$ over all test cases does not exceed 250ドル,000円$.

It is guaranteed that the sum of $q$ over all test cases does not exceed 250ドル,000円$.

출력

For each of the $q$ queries, output the answer separated by lines.

제한

노트

The following list shows the possible optimal assignments for each query for the first test case:

• $[18,24,2,26,18]$
• $[22,28,6,30,22]$
• $[4,7,0,9,1]$
• $[7,13,0,15,7]$
• $[13,19,0,21,13]$