| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 32 | 9 | 7 | 25.000% |
경곽에는 아주 거대한 정화조 시설이 있다. 정화조의 구조는 다음과 같다. 먼저 원천(source)에서 여러 개의 펌프를 이용해서 물을 퍼 올린다. 물은 수도관을 따라 여러 정화조 시설을 거치게 된다. 수도관은 한 정화조와 다른 정화조를 이어주는 역할을 한다. 수도관은 트리 형태의 간선 구조를 가지고 있다. 다시 말하면 수도관을 따라 물이 이동할 때 한 정화조를 두 번 이상 지나지 않으며, 펌프에서 퍼 나른 물들은 모두 최종적으로 한 정화조로 모이는 구조를 지니고 있다. 위 그림에서 동그라미는 정화조를, 화살표는 수도관을 나타낸 것이다. 펌프에서 퍼 올린 물은 최초로 트리의 리프에 존재하는 정화조로 이동한다. (여기서 리프란 자기에게로 향하는 수도관이 없는 정화조를 의미한다.)
물은 수질에 따라 여러 등급으로 분류할 수 있다. 가장 깨끗한 물은 0등급이고, 1등급, 2등급, 3등급, $\ldots$ 순으로 물이 더러워진다. 처음에 원천에서의 물은 0등급이다. 물이 수도관을 따라 한 정화조에서 다른 정화조로 이동할 때마다 물은 오염되고 수질은 한 등급 오른다. 정화조에 처음 도착한 물의 수질도 1등급이라고 본다.
물이 정화조를 지날 때, 정화조는 이 물을 정화할 수도 있고, 그대로 흘려보낼 수도 있다. 정화조에는 고유 비용 $c_i$가 존재한다. 정화조에서 물을 정화할 경우, $c_i$ × (정화할 물의 수질 등급) 만큼의 비용이 소모되며, 물은 0등급으로 정화된다. 만약 물을 정화하지 않을 경우, 아무 비용도 지출하지 않으며 물의 수질도 변하지 않는다.
정화조의 효율적인 운영을 위해 각 정화조마다 두 수 $l_i$, $r_i$ ($l_i \leq r_i$) 가 주어진다. 이는 $i$번째 정화조는 $l_i$ 이상 $r_i$ 이하 등급의 수질을 갖는 물만 정화할 수 있다는 의미이다.
경곽은 막대한 정화조 공사를 위해 일시적으로 정화조의 운영을 중단하려고 한다. 정화조의 운영을 중단한다는 것은 물이 그 정화조를 지나갈 수 없도록 만든다는 것이다. 다만 경곽으로의 물 공급이 끊기면 안 되기 때문에, 몇 가지 정화조는 그대로 운영하려고 한다. 경곽에겐 쿼리가 주어진다. 각 쿼리에는 정화조 번호 $X$와 수질 $K$가 주어진다. 경곽은 원천과 정화조 $X$를 잇는 한 경로를 제외하고 나머지 정화조는 모두 중단하려고 한다. 이때, $X$에서 $K$등급 이하의 물을 얻으려면 최소 몇의 비용을 필요로 하는지 구해야 한다.
경곽의 문제를 같이 해결해 주자. 쿼리는 다른 쿼리와 서로 독립적이다. 즉, 한 쿼리에서 중단시킨 정화조가 다음 쿼리에서도 무조건 중단되는 것은 아니다.
첫 번째 줄에 정화조의 개수 $N$이 주어진다.
두 번째 줄에 $N$개의 정수 $c_1, c_2, \ldots, c_N$이 주어진다. $c_i (1 \leq i \leq N)$는 $i$번째 정화조의 고유 비용을 의미한다.
다음 $N$개의 줄에 걸쳐 수도관이 정화할 수 있는 수질 등급의 범위 $l_i, r_i$가 주어진다. $(l_i \leq r_i)$
다음 $N - 1$개의 줄에 걸쳐 수도관에 대한 정보가 주어진다. 각 줄에는 $u_i, v_i (1 \leq i \leq N - 1)$이 주어진다.
이는 $u_i$번째 정화조에서 $v_i$번째 정화조로 수도관이 이어져 있다는 것을 의미한다.
다음 줄에는 쿼리의 개수 $Q$가 주어진다.
다음 $Q$개의 줄에 걸쳐 각 줄에 두 정수 $X_i, K_i$가 주어진다.
이는 정화조 $X_i$와 원천을 잇는 한 경로에서 $K_i$ 이하의 수질 등급을 얻으려고 할 때 필요한 최소 비용을 출력하라는 의미이다.
$Q$개의 줄에 걸쳐 각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.
만약 $K_i$ 이하의 수질 등급의 물을 얻을 수 없다면 -1을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $1 \leq N, Q \leq 1000$ |
| 2 | 30 | $l_i=1,r_i=N$ $(1\leq i\leq N)$ $K_i=0$ $(1\leq i\leq Q)$ |
| 3 | 60 | 추가 제한 조건이 없다. |
5 1 2 3 4 5 1 2 3 3 1 5 4 5 1 3 2 1 3 2 4 2 5 1 3 1 1 1 3 2 0
2 0 -1
School > 경기과학고등학교 > IamCoder Qualification Test > 2023 IamCoder Qualification Test F번