Tree Path with All Critical Nodes

You are given an undirected, weighted tree with n nodes and n-1 edges. In addition, k of its nodes are marked as critical (each critical node contains a glowing ball). In q queries, you are given two nodes s and t. For each query, determine the minimum total length of a path starting at s and ending at t that visits every critical node at least once.

The answer for each query is defined as the minimum distance required to cover the set S = {s, t} ∪ K (where K is the set of all critical nodes). It can be shown that in a tree the minimum route covering a set of nodes equals

[ \text{Answer} = 2 \times \left(\sum_{e \in T_S} w_e\right) - \text{diameter}(T_S), ]

where T_S is the minimal subtree spanning all nodes in S, \(w_e\) is the weight of an edge in T_S, and diameter(T_S) is the longest distance between any two nodes in T_S measured along the tree.

Note: All formulas are in LaTeX format.

inputFormat

The first line contains three integers n, q, and k — the number of nodes, the number of queries, and the number of critical nodes, respectively.

The next n-1 lines each contain three integers u, v, and w, indicating that there is an edge between nodes u and v with weight w.

The following line contains k distinct integers representing the indices of the critical nodes.

Each of the next q lines contains two integers s and t, representing the start and end nodes for that query.

outputFormat

For each query, output a single line containing the minimum total length of a path from s to t that passes through every critical node at least once.

sample

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

13
22
13