cho.sh

레이무의 순간이동 연습

아직 제출이 없습니다시간 제한6초메모리 제한1024 MB

문제

레이무가 사는 환상향에는 NN 개의 신사가 있습니다. 이 중 KK 개의 신사는 명신을 모시는 명신대사입니다. 두 신사를 양방향으로 잇는 길이 N−1N-1 개 있고, 임의의 두 신사를 한 개 이상의 길을 사용해 오갈 수 있습니다. QQ 일 동안 레이무는 자신의 능력인 순간이동을 연습하기로 했습니다. ii 번째 날에는 A_iA\_i 번 신사에서 시작해서 마리사가 있는 B_iB\_i 번 신사까지 가려고 합니다. 레이무는 다음 동작을 이용해 신사 사이를 이동합니다.

  • 현재 신사와 길로 직접 연결된 다른 신사 중 하나를 선택해서 이동합니다.
  • 지금 있는 신사가 명신대사이면, 지금 있는 신사를 포함한 KK 개의 명신대사 중 하나에 동일한 확률로 무작위로 순간이동 합니다.

마리사는 레이무가 빨리 연습을 끝내고 놀아주기를 원하기 때문에 어떤 순서로 동작을 사용해야하는지 알려주려고 합니다. 매 순간 B_iB\_i 번 신사까지 도착하기 위해 사용하는 동작 횟수의 기댓값이 최소가 되는 선택을 한다고 할 때, A_iA\_i번 신사에서 B_iB\_i번 신사까지 가는 동작 횟수의 기댓값을 출력하세요.

입력

첫 줄에 N,K,QN, K, Q가 공백으로 구분되어 주어집니다. (2≤N≤100,000;1≤K≤N;1≤Q≤500,000)(2 \le N \le 100\\,000; 1 \le K \le N; 1 \le Q \le 500\\,000)

다음 N−1N-1 개의 줄의 ii 번째 줄에는 u_i,v_iu\_i, v\_i가 주어집니다. 이는 u_iu\_i번 신사와 v_iv\_i번 신사가 길로 연결되어있다는 것을 의미합니다. (1≤u_i<v_i≤N)(1 \le u\_i < v\_i \le N) 임의의 두 신사를 한 개 이상의 길을 사용해 오갈 수 있다는 것이 보장됩니다.

다음 줄에 명신대사의 신사 번호 p_1,p_2,⋯ ,p_Kp\_1, p\_2, \cdots, p\_K가 주어집니다. (1≤p_1<p_2<⋯<p_K≤N)(1 \le p\_1 < p\_2 < \cdots < p\_K \le N)

다음 QQ 개의 줄의 ii 번째 줄에는 A_i,B_iA\_i, B\_i가 주어집니다. 이는 ii 번째 날에 A_iA\_i 번 신사에서 시작해서 B_iB\_i 번 신사까지 간다는 의미입니다. (1≤A_i,B_i≤N;A_i≠B_i)(1 \le A\_i, B\_i \le N; A\_i \neq B\_i)

출력

QQ 개의 줄을 출력합니다. ii번째 줄에는 A_iA\_i 번 신사에서 B_iB\_i 번 신사로 도착하기 위한 동작 횟수의 기댓값을 출력합니다.

정답과의 상대 오차가 10−910^{-9} 이하여야 합니다.