Winter Forest and the Magic Flame

The $N$ villages in the winter forest are connected by $N - 1$ undirected roads. Every road has a positive integer length, and the road network forms a tree.

The first village has a magic flame, and the people of the winter forest live on the warmth of this flame. The distance from the village with the flame to another village is the sum of the road lengths on the path to that village.

The king of the forest is also its most powerful wizard. Using magic, he can shorten the roads. For each road, spending $K$ units of magic power, where $K$ is a positive integer, shortens that road by $K$. However, no matter how much magic power is spent, a road cannot be shortened below $1$.

The king wants to shorten the distance from the flame village to the farthest village as much as possible. If he uses at most $B$ units of magic power, how far can this distance be reduced?

The first line contains the number of villages $N$ ($2 \leq N \leq 200,000$).

Each of the next $N - 1$ lines contains two endpoints $A_{j}$, $B_{j}$ ($1 \leq A_{j}, B_{j} \leq N$, $A_{j} \neq B_{j}$) and the length $W_{j}$ ($1 \leq W_{j} \leq 10^{9}$) of a road.

The next line contains the number of magic power queries $Q$ ($1 \leq Q \leq 200,000$).

Each of the next $Q$ lines contains the magic power $B_{i}$ for one query ($0 \leq B_{i} \leq 2 \times 10^{14}$).

For each query, print the minimum possible distance between the village with the flame and the farthest village, given the magic power available for that query. Print one answer per line.