\(N\)개의 도시와 \(M\)개의 도로 후보가 있다.

각 도로 후보는 두 도시를 연결하며, 건설 비용이 정해져 있다.

\(Q\)개의 질의가 주어진다.
각 질의는 정수 \(x\) 하나로 이루어져 있다.

비용이 \(x\) 이하인 도로들만 건설할 수 있다고 할 때, 서로 이동 가능한 도시 쌍의 개수를 구하시오.

두 도시 \(a, b\)가 같은 연결 요소에 속한다면 두 도시는 서로 이동 가능하다고 한다.

도시 쌍 \((a, b)\)와 \((b, a)\)는 같은 쌍으로 세며, \(a = b\)인 경우는 세지 않는다.

\(1 ≤ N ≤ 200\,000\)
\(0 ≤ M ≤ 200\,000\)
\(1 ≤ Q ≤ 200\,000\)
\(1 ≤ a, b ≤ N\)
\(a ≠ b\)
\(1 ≤ c ≤ 1\,000\,000\,000\)
\(0 ≤ x ≤ 1\,000\,000\,000\)
같은 두 도시를 연결하는 도로는 최대 한 개만 주어진다.
정답은 int 범위를 넘을 수 있으므로 64비트 정수를 사용해야 한다.

첫째 줄에 도시의 개수 \(N\), 도로 후보의 개수 \(M\), 질의의 개수 \(Q\)가 주어진다.

둘째 줄부터 \(M\)개의 줄에 걸쳐 도로 정보가 주어진다.

각 도로 정보는 세 정수 \(a\) \(b\) \(c\)로 이루어져 있다.

이는 도시 \(a\)와 도시 \(b\)를 연결하는 도로의 건설 비용이 \(c\)라는 뜻이다.

그 다음 줄부터 \(Q\)개의 줄에 걸쳐 질의가 주어진다.

각 질의는 정수 \(x\) 하나로 이루어져 있다.

각 질의마다 비용이 \(x\) 이하인 도로들만 사용할 수 있을 때, 서로 이동 가능한 도시 쌍의 개수를 한 줄에 하나씩 출력한다.

anthony0506 작성

출처 anthony0506