Tree Paths with Key Nodes

This problem is a variant of Stage5 with a different definition for a valid path. You are given an unrooted tree with n nodes and weighted edges, and k key nodes. There are q queries; each query gives two nodes s and t. Your task is to compute the minimum distance of any path from s to t that passes through at least one key node. Note that if s or t is a key node, the direct path from s to t is already valid.

The tree is undirected and connected, and each edge has a positive weight. All nodes are numbered from 1 to n.

The answer for each query is defined as:

[ answer = \min_{x \in \text{keys}}{ d(s,x) + d(x,t) }]

where d(u,v) denotes the distance between nodes u and v along the tree. Use binary lifting (LCA) to compute distances efficiently.

inputFormat

The first line contains three integers n, k, and q (n nodes, k key nodes, and q queries).

The second line contains k distinct integers representing the key nodes.

Each of the next n-1 lines contains three integers u, v, and w indicating that there is an edge between nodes u and v with weight w.

Each of the next q lines contains two integers s and t, representing a query.

outputFormat

For each query, output a single integer representing the minimum distance of a valid path from s to t that passes through at least one key node.

sample

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

10
2
5