타워 디펜스

시간 제한5초메모리 제한1024 MB

요약

나무 모양 도로망에서 모든 타워가 보호하는 도시를 하나 고르고, 반경을 x만큼 늘릴 때 드는 ceil(x/k) 비용의 합을 최소화합니다.

난이도: 어려움10점 중 8점
유형: 트리, 분할 정복, 수학
정답자: 아직 제출이 없습니다

문제

Byteland 왕국의 도로망은 $1$ 부터 $n$ 까지 번호가 매겨진 $n$ 개의 도시로 이루어지며, 양방향 도로 $n-1$ 개로 연결되어 있다. 각 도로의 길이는 $1$ 이다. 도로망은 연결되어 있고 그래프는 트리이다.

왕국에는 $m$ 개의 군사 타워가 있다. $i$ 번째 타워는 도시 $a_i$ 에 있고, 반경 $r_i$ 의 보호 구역을 가진다. 도시 $v$ 는 $v$ 와 $a_i$ 사이의 이동 거리가 $r_i$ 이하이면 타워 $i$ 의 보호를 받는다.

왕은 도시 하나를 새 수도로 고른다. 수도는 모든 타워의 보호를 받아야 한다. 왕은 기존 타워 중 어느 것이든 보호 반경을 늘릴 수 있다. 타워의 반경을 음이 아닌 정수 $x$ 만큼 늘리는 데는 $\lceil\frac{x}{k}\rceil$ 코인이 든다. 모든 타워의 보호를 받는 수도를 고를 수 있도록 왕이 써야 하는 코인 총액의 최솟값을 구하라.

입력

첫 줄에 세 정수 $n$ , $m$ , $k$ ( $1\leq n, m\leq 10^5$ , $1\leq k\leq 10$ )가 주어진다. 각각 도시의 수, 타워의 수, 비용 함수의 나눗수이다.

다음 $n-1$ 줄은 도로를 나타낸다. $i$ 번째 줄에는 $i$ 번째 도로가 잇는 두 도시의 번호 $u_i$ , $v_i$ ( $1\leq u_i, v_i\leq n$ )가 주어진다. 주어지는 그래프는 트리임이 보장된다.

이어지는 $m$ 줄은 타워를 나타낸다. $i$ 번째 줄에는 $i$ 번째 타워가 있는 도시 $a_i$ 와 보호 반경 $r_i$ ( $1\leq a_i\leq n$ , $0\leq r_i\leq 10^9$ )가 주어진다.

출력

새 수도를 고를 수 있도록 타워를 강화하는 데 필요한 코인의 최솟값을 정수 하나로 출력한다.

예제3

예제 1
입력
```
3 2 1
1 2
2 3
1 1
3 0
```
예상 출력
```
1
```
예제 2
입력
```
5 2 1
1 2
2 3
3 4
4 5
1 0
5 0
```
예상 출력
```
4
```
예제 3
입력
```
6 2 2
1 2
2 3
3 4
4 5
5 6
1 0
6 2
```
예상 출력
```
2
```