27605번 - 기지 간소화 서브태스크언어 제한함수 구현

먼 미래, 인류는 수많은 외계 행성들에 진출하였다. 행성 X도 그 중 하나로, 우주 탐사 기업 MR은 행성 X에 기지들을 지어 탐사 및 자원 채취 활동을 수행하고 있었다.

행성 X에는 $N$개의 기지와 기지들을 잇는 $N-1$개의 양방향 통로가 있으며, 임의의 서로 다른 두 기지를 통로만을 사용하여 오갈 수 있다. 즉, 행성 X의 기지와 통로는 트리 구조를 이룬다.

기지에는 각각 $0$ 이상 $N - 1$ 이하의 서로 다른 번호가 붙어 있다. 또 모든 $0\le i \le N-2$에 대해서 $i$번 도로는 $U[i]$번 도시와 $V[i]$번 도시를 연결하며 통로의 길이는 $W[i]$ km이다.

어느덧 행성 X의 개발도 안정기에 접어들었다. 모든 기지와 통로를 유지하는 것은 비용이 많이 들기 때문에, MR에서는 일부 기지들만 남기고 나머지를 비활성화하기로 하였다.

어떤 $(s, e)$ ($0 \le s \le e \le N - 1$) 에 대해 $s, s+1, \dots, e$번 기지만 남기기로 했다고 하자. 이 때 유지 비용은 다음과 같이 정의된다.

• 0개 이상의 통로를 골라 다음 조건을 만족시키자. 이 때, 고른 통로들의 길이의 합이 최소가 되도록 고른다. (통로를 $0$개 고른 경우, 길이의 합은 $0$ km 이다.)
  • 임의의 $u, v$ ($s \le u < v \le e$)에 대해, $u$번 기지와 $v$번 기지를 고른 통로들만 이용해서 서로 오고갈 수 있다. 중간에 비활성화된 기지를 거치는 것은 상관 없다.
• 고른 통로들의 길이의 합이 $C$ km일 때, 유지 비용은 $C$ 이다.

여러분은 아래 함수를 구현해야 한다.

int maintenance_costs_sum(vector<int> U, vector<int> V, vector<int> W)

• 이 함수는 단 한 번만 호출된다.
• $U$, $V$, $W$: 크기가 $N-1$인 정수 배열. 모든 $i$ ($0 \le i \le N - 2$)에 대해, $U[i]$번 기지와 $V[i]$번 기지를 잇는 길이 $W[i]$ km의 통로가 있다.
• 이 함수는 가능한 모든 ($i, j$) ($0 \le i \le j \le N - 1$) 쌍에 대해 $i, i+1, \dots, j$번 기지만 남겼을 때의 유지 비용을 모두 합한 값을 $1\,000\,000\,007$로 나눈 나머지를 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

• $2 \le N \le 250\,000$
• 모든 $i$에 대해 $0 \le U[i], V[i] \le N-1$; $U[i] \neq V[i]$ ($0 \le i \le N - 2$)
• 모든 $i$에 대해 $1 \le W[i] \le 10^9$ ($0 \le i \le N - 2$)

$N = 5$, $U = [0, 2, 2, 0]$, $V = [2, 1, 4, 3]$, $W = [2, 3, 6, 5]$인 경우를 생각해 보자.

그레이더는 다음 함수를 호출한다.

maintenance_costs_sum([0, 2, 2, 0], [2, 1, 4, 3], [2, 3, 6, 5])

아래 그림은 행성 X의 기지 및 통로의 배치를 나타낸다.

모든 가능한 $(i, j)$ 쌍에 대해 유지 비용을 각각 구해 보면 아래의 표와 같다.

함수는 $98$을 반환해야 한다.

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1: $N$
• Line $2+i$ $(0 \le i \le N - 2)$: $U[i]$ $V[i]$ $W[i]$

Sample grader는 다음을 출력한다.

• Line 1: maintenance_costs_sum이 반환한 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• base.zip