Escape The Maze

Alice is currently trapped in a maze, which can be seen as a $\textbf{tree}$. Each edge in the tree has a weight representing the length of that edge. The leaves of the tree represent the exits, and when Alice reaches a leaf, it means she has successfully escaped from the maze.

A leaf is defined as a node with degree 1 that is not the root.

Each maze has a difficulty level, denoted as $L$. When Alice is at a node $x$ in the tree, she can choose to jump to a node $y$ in her subtree. Let $s$ be the sum of the edge weights along the path from $x$ to $y$. The energy spent when jumping from $x$ to $y$ is $(s-L)^2$.

Alice wants to know the minimum amount of energy required to escape the maze if the tree has $p$ as the root and she starts from $p$. Alice will ask this question a total of $Q$ times.

The data guarantees that for any given pair of points $x$ and $y$, the absolute value of the sum of edge weights $s$ along the path between them does not exceed $10^9$.

The input consists of multiple test cases. The first line contains a single integer $T(1≤T≤5)$ — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n,L$ $(3≤n≤10^5,-10^5\le L\le 10^5) $— the number of nodes in the tree.

Each of the next $n-1$ lines contains three integers $u,v,w$ $(1\le u , v\le n , u\neq v , -10^5\le w \le 10^5)$

The next line contains a positive integer $Q$ $(1\le Q\le 10)$。

Each of the next $Q$ lines contains one integer $p$ $(1\le p\le n)$ asks the minimum amount of energy required to escape the maze if the tree has $p$ as the root and she starts from $p$.

It is guaranteed that the given graph is a tree.

For each test case, output $Q$ lines. Each line should contain a integer indicating the minimum amount of energy required.

The data guarantees that the answer will not exceed the range that can be represented by a 64-bit signed integer.

1
4 2
1 2 5
1 3 -4
1 4 6
4
1
2
3
4

9
1
0
0

2023“钉耙编程”中国大学生算法设计超级联赛（1）