풍력 터빈

Anna는 North Sea에 새로 건설되는 해상 풍력 발전 단지의 배선을 설계하는 임무를 맡았다. 이 발전 단지는 $N$개의 터빈으로 구성되며, 터빈에는 $0, 1, \ldots, N-1$의 번호가 매겨져 있다. Anna의 목표는 모든 터빈을 가능한 한 저렴하게 육지에 연결하는 것이다.

Anna에게는 가능한 연결 $M$개의 목록이 있으며, 각 연결은 두 풍력 터빈을 잇고 특정 비용을 가진다. 또한 인근 도시는 연속한 터빈 구간 $[\ell, r]$을 육지에 연결하는 비용을 부담하기로 했다. 즉, 이 범위의 각 터빈 $t$는 ($\ell\le t\le r$) 육지에 무료로 직접 연결된다. 가능한 모든 연결을 건설하면 임의의 풍력 터빈에서 다른 임의의 풍력 터빈으로 도달할 수 있다. 따라서 풍력 터빈 중 하나라도 육지에 연결되는 즉시, 모든 터빈의 전력을 육지로 전달할 수 있도록 연결을 건설하는 것이 가능하다. 물론 육지로 연결되는 터빈이 더 많으면 총비용이 더 저렴해질 수 있다. 무료 연결만이 육지로 직접 이어지는 연결임에 유의한다.

Anna는 모든 풍력 터빈이 (다른 풍력 터빈을 거칠 수도 있게) 육지에 도달할 수 있도록 하면서 비용의 합을 최소화하는 방식으로 가능한 연결의 부분집합을 선택해야 한다.

현명한 결정을 내릴 수 있도록 도시는 구간 $[\ell, r]$에 대해 가능한 선택지 $Q$개를 Anna에게 제공한다. 도시는 Anna에게 각 시나리오의 최소 비용을 계산해 달라고 요청한다.

제약 조건 및 채점

• $2 \le N\le 100\,000$.

• $1 \le M\le 100\,000$.

• $1 \le Q\le 200\,000$.

• $0 \le u_i,v_i \le N-1$.

• $u_i \ne v_i$, 그리고 각 풍력 터빈 쌍 사이에는 직접 연결이 최대 하나 존재한다.

• $1 \le c_i \le 1\,000\,000\,000$.

• $0 \le \ell_i\le r_i \le N-1$.

여러분의 풀이는 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 평가된다. 각 테스트 그룹은 테스트 케이스들의 집합을 포함한다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

1 | 8 | $M=N-1$이고, $i$번째 연결은 $u_i=i$ 및 $v_i=i+1$을 가진다. 즉, 모든 연결을 건설하면 경로 $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N-1$를 이룬다

2 | 11 | $N,M,Q\le 2\,000$이고 $\sum(r_i-\ell_i+1) \le 2\,000$

3 | 13 | 모든 $i$에 대해 $r_i=\ell_i+1$

4 | 17 | 모든 $i$에 대해 $1\le c_i \le 2$. 즉, 각 연결의 비용은 $1$ 또는 $2$이다

5 | 16 | $\sum(r_i-\ell_i+1)\le 400\,000$

6 | 14 | 모든 $i$에 대해 $\ell_i=0$

7 | 21 | 추가 제약 조건 없음

예제

첫 번째 예제에서는 다음과 같은 가능한 연결의 그래프가 주어진다.

세 가지 시나리오가 주어진다. 첫 번째 시나리오에서는 터빈 1만 육지로 연결되어 있다. 이 경우 터빈 $0$와 터빈 $2$ 사이의 연결을 제외한 모든 연결을 유지해야 하며, 총비용은 $2+3+6+3=14$이다. 다음 시나리오에서는 터빈 3와 4이 육지에 연결되어 있다. 이 경우 연결 $(1,0)$, $(1,2)$, $(2,4)$를 유지하며, 비용은 8이다. 세 번째 시나리오에서는 터빈 0을 제외한 모든 터빈이 육지에 연결되어 있다. 이 경우 이 터빈 하나만 다른 터빈에 연결하면 되며, 이를 위해 연결 $(0,1)$를 선택한다. 각 시나리오의 해는 아래에 나타나 있다.

|

|

첫 번째와 여섯 번째 예시는 테스트 그룹 2, 5, 7의 제약 조건을 만족한다. 두 번째와 일곱 번째 예시는 테스트 그룹 1, 2, 5, 7의 제약 조건을 만족한다. 세 번째 예시는 테스트 그룹 2, 3, 5, 7의 제약 조건을 만족한다. 네 번째 예시는 테스트 그룹 2, 4, 5, 7의 제약 조건을 만족한다. 다섯 번째 예시는 테스트 그룹 2, 5, 6, 7의 제약 조건을 만족한다.

입력의 첫 번째 줄에는 세 정수 $N$, $M$, $Q$가 주어진다.

이어지는 $M$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $c_i$가 주어진다. $i$번째 줄은 풍력 터빈 $u_i$와 $v_i$ 사이의 비용이 $c_i$인 가능한 연결을 나타낸다. 이 연결들은 무방향이며 서로 다른 두 터빈을 연결한다. 같은 터빈 쌍을 연결하는 두 연결은 존재하지 않는다. 가능한 모든 연결을 건설하면 임의의 풍력 터빈에서 다른 임의의 풍력 터빈으로 (직접 또는 간접적으로) 도달할 수 있음이 보장된다.

다음 $Q$개의 줄에는 각각 두 정수 $\ell_i$, $r_i$가 주어지며, 육지가 풍력 터빈 $\ell_i,\ell_i+1,\ldots,r_i$에 직접 연결되는 시나리오를 나타낸다. 육지가 풍력 터빈 하나에만 직접 연결되는 경우에는 $r_i = \ell_i$일 수 있음에 유의한다.

시나리오마다 한 줄씩, $Q$개의 줄을 출력한다. 각 줄에는 모든 터빈이 전력을 육지로 전달할 수 있도록 연결하는 최소 비용인 정수 하나를 출력한다.