| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 70 | 16 | 14 | 35.897% |
$N$개의 도시와 $N-1$개의 도로로 이루어진 국가가 있다. 도시에는 $1$부터 $N$까지의 번호가 붙어 있고, 도로에도 $1$부터 $N-1$의 번호가 붙어 있다. $i$번 도로는 $A_i$번 도시와 $B_i$번 도시를 양방향으로 연결하고, 이동 시에는 $W_i$의 비용이 든다. 임의의 두 도시를 고르더라도 둘 사이를 하나 이상의 도로를 사용하여 왕복할 수 있음이 보장된다.
두 도시 사이의 거리를 한 도시에서 출발하여 하나 이상의 도로를 거쳐 다른 도시로 갈 때 필요한 최소 비용으로 정의하자.
당신은 도로 회사의 사장으로, 명절을 맞아 할인 행사를 진행하려고 한다. 할인 행사를 위한 총 $Q$개의 계획이 있다. $i$번째 계획에서는 $X_i$번 도시에서 출발하여 $Y_i$번 도시로 가는 최단 경로에 속하는 모든 도로들에 할인을 적용하여 비용을 0으로 만들 것이다. 각 할인 행사 계획에 대해, 두 도시 사이 거리의 최댓값을 출력하라.
첫 번째 줄에 도시의 수를 나타내는 정수 $N$이 주어진다.
다음 $N-1$개의 줄 중 $i$번째 줄에는 세 정수 $A_i$, $B_i$, $W_i$가 공백으로 구분되어 주어진다. 이들은 $i$번째 도로가 연결하는 두 도시의 번호와 도로의 이동 비용을 나타낸다.
다음 줄에 계획의 수를 나타내는 정수 $Q$가 주어진다.
다음 $Q$개의 줄 중 $i$번째 줄에는 두 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. 이들은 $i$번째 계획을 나타낸다.
총 $Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 계획에 대한 답을 출력해야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N, Q \le 2\,000$ |
| 2 | 24 | $X_i=1$ ($1 \le i \le Q$) |
| 3 | 27 | $Q=N-1$; $X_i = A_i$; $Y_i = B_i$ ($1 \le i \le N-1$) |
| 4 | 39 | 추가적인 제약 조건이 없다. |
5 1 2 1 1 3 2 2 4 4 2 5 2 3 1 4 3 5 5 4
4 4 3
5 1 2 2 1 3 3 1 4 5 1 5 4 3 1 2 1 4 4 5
9 7 5
8 1 2 3 1 3 5 2 4 5 2 5 3 2 6 6 6 7 1 6 8 2 7 1 2 1 3 2 4 2 5 2 6 6 7 6 8
13 13 16 16 13 16 15
7 1 2 3 1 3 4 2 4 2 2 5 1 3 6 6 3 7 2 6 1 2 1 3 1 4 1 5 1 6 1 7
12 11 11 12 7 11
University > KAIST > KAIST RUN Spring Contest > 2024 KAIST RUN Spring Contest F번