26221번 - 겨울 숲과 마법 불꽃

문제

겨울 숲 속의 $N$개의 마을은 $N - 1$개의 무방향 도로로 연결되어 있다. 모든 도로의 길이는 양의 정수이며 도로망은 트리 구조를 이루고 있다.

첫 번째 마을에는 마법의 불꽃이 존재해 겨울 숲의 사람들은 이 불꽃에서 나오는 온기로 살아간다. 불꽃이 있는 마을에서 다른 마을까지의 거리는 그 마을까지의 경로 상에 있는 도로의 길이의 합이다.

가장 강대한 마법사이기도 한 숲의 왕은 마법의 힘을 사용해 도로의 길이를 줄일 수 있다. 각 도로에 대해 왕의 마법력을 양의 정수 $K$만큼 소모하면 도로의 길이를 $K$만큼 줄일 수 있다. 하지만 마법력을 아무리 많이 써도 도로의 길이를 1ドル$ 미만으로 줄일 수는 없다.

왕은 불꽃이 있는 마을부터 가장 먼 마을까지의 거리를 최대한 줄이고 싶어한다. 마법력을 최대 $B$ 사용한다면 이를 어디까지 줄일 수 있는가?

입력

첫 번째 줄에 마을의 수 $N$ (2ドル \leq N \leq 200,000$)이 주어진다.

다음 $N - 1$개의 줄에 각 도로의 양끝 마을의 번호 $A_{j},ドル $B_{j}$ (1ドル \leq A_{j}, B_{j} \leq N,ドル $A_{j} \neq B_{j}$)와 그 도로의 길이 $W_{j}$ (1ドル \leq W_{j} \leq 10^{9}$)가 주어진다.

다음 줄에 마법력에 대한 쿼리의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 200,000$)

다음 $Q$개의 줄에 각 쿼리에서의 마법력 $B_{i}$가 주어진다. (0ドル \leq B_{i} \leq 2 \times 10^{14}$)

출력

각각의 쿼리에 대해, 쿼리에서 주어진 마법력을 사용할 수 있을 때 불꽃이 있는 마을과 가장 먼 마을과의 거리의 최소값을 출력한다.

제한

힌트