지하철

Stomholck에서는 지하철망이 트리 형태이며, 버스와 달리 지하철은 대체로 제시간에 온다. 당신은 지하철망에서 $m$번의 이동을 할 계획이며, 가능한 한 저렴하게 이동하려고 한다.

두 역 사이를 이동하는 비용은 역 사이 경로의 간선마다 1크로나이다. 또한 임의로 선택한 두 역 사이의 모든 간선에서 추가 비용 없이 횟수 제한 없이 이동할 수 있는 카드를 구매할 수 있다. 카드의 비용은 선택한 경로의 간선마다 $k$크로나이며, 고객은 카드를 하나보다 많이 구매할 수 없다. 원하지 않는다면 카드를 구매하지 않아도 된다. 지하철망은 트리이므로 모든 정점 쌍 사이에는 항상 정확히 하나의 경로가 있다.

$n$개의 역과 $m$번의 이동이 주어진 지하철망에서, 모든 이동을 하는 데 드는 최소 비용을 구한다.

점수

제출한 해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $19$ | $2 \le n, m \le 50$

$2$ | $26$ | $2 \le n, m \le 1000$

$3$ | $20$ | $2 \le n, \le 20000$ , $0 \le m \le 1000$

$4$ | $35$ | 추가 제한이 없다.

첫 번째 줄에는 세 정수 $n$, $m$, $k$이 주어진다 ($2 \leq n \leq 10^5$, $0 \leq m, k \leq 10^5$). 다음 $n-1$개의 줄에는 두 정수 $u_i$와 $v_i$가 주어지며 ($1 \leq u_i , v_i \leq n$ , $u_i \neq v_i$), 이는 정점 $u_i$과 $v_i$ 사이에 간선이 있음을 의미한다. 그다음 $m$개의 줄에는 두 정수 $a_i$와 $b_i$가 주어지며 ($1 \leq a_i , b_i \leq n$ , $a_i \neq b_i$), 이는 $i$번째 이동이 $a_i$과 $b_i$ 사이의 이동임을 의미한다.

한 사람이 $m$번의 이동을 모두 하는 데 드는 최소 비용을 나타내는 정수 하나를 출력한다.

카드를 구매하지 않으면 두 번의 이동 비용은 $7$이다. 반면 $2$과 $5$ 사이의 카드를 구매하면 두 크로나를 절약하므로 비용은 $5$가 된다.

여기서는 카드를 전혀 구매하지 않는 편이 낫다.