26155번 - 배수관 미스터리

문제

최근 대량의 폭우로 인해 침수 문제가 심각해진 결과, 한양대학교에서도 이를 위한 대비책을 미리 준비하고자 한다!

캠퍼스 내에는 $N$개의 배수구가 랜덤하게 배치되어 있고, 배수구들을 잇는 $M$개의 지하 배수관들이 존재한다. 하지만 캠퍼스가 고지에 위치하다 보니 침수에 대한 걱정을 하지 않게 되어 배수관들이 오랜 시간 방치되어왔고, 더 이상 해당 배수구들이 제 역할을 할 수 있는지 확인할 수 없는 지경에 이르렀다!

모든 배수관의 상태에 대한 전수조사를 피하기 위해, 세정이는 각 배수관의 설치 일자를 고려하여 해당 배수관이 정상적으로 연결되어 있을 확률 $p$를 계산해냈다. 이 배수관들은 모두 동일 업체에서 동일 자재로 만들었기 때문에, 모든 배수관의 연결 확률 $p$는 동일한 확률 변수를 가진다고 가정하자.

세정이는 여러 상황을 고려하여 연결되어 있을 배수구들의 집합 개수를 미리 계산해보고자 한다. 임계 확률 $p'$이 주어질 때, 연결 확률이 $p'$이상인 배수관들은 전부 연결된 것으로 가정한다면 연결된 배수구들의 집합 개수는 총 몇 개일지 구해보자!

단, 다른 배수구와 이어지지 않은 배수구 또한 집합 1개라고 가정한다. 문제에서 주어지는 모든 확률 값은 소수 네 자릿수로 주어진다.

입력

첫 번째 줄에 배수구의 개수 $N$ (1ドル \le N \le 100\ 000$), 각 배수구를 연결하는 배수관의 개수 $M$ (1ドル \le M \le 300\ 000$)이 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 각 배수관의 정보 $(a, b, p)$가 순서대로 주어진다. 이때 $a, b$ (1ドル \le a, b \le N$)는 배수관이 연결하는 두 정점을 의미하고, $p$ (0ドル \le p \le 1$)는 해당 배수관이 연결되어 있을 확률을 의미한다.

$M+1$번째 줄에 주어질 질의의 개수 $Q$ (1ドル \le Q \le 100\ 000$)가 주어진다.

이후 $Q$개의 줄에 걸쳐 질의할 임계 확률 $p'$ (0ドル \le p' \le 1$)가 주어진다.

출력

$Q$개의 줄에 걸쳐 해당 임계 확률이 적용될 때 연결되어 있는 배수관 네트워크의 개수를 출력하라.

제한

힌트