BOJ 18365 Visits

문제 링크:

문제 내용

정점의 개수가 $n$ 인 트리가 주어집니다. 정점 $i$ 의 가중치는 $c_i$ 입니다.

이 트리에서 $t_1, t_2, \cdots, t_n$ 번 정점을 순서대로 방문하려고 합니다. 여기서 $\{t_i\}$ 는 순열입니다. 즉, 1부터 $n$ 까지의 정수가 정확히 한 번씩 등장합니다.

$1 \le i \le n - 1$ 에 대해, $t_i$ 번 정점과 $t_{i+1}$ 번 정점을 잇는 경로 상에서 $k_i$ 개의 간선을 통과할 때마다 만나는 정점들(시작점과 끝점 포함)의 가중치의 합을 구하세요. $k_i$ 는 $i$ 번째 경로의 길이의 약수임이 보장됩니다.

입력

첫 줄에 $n$ 이 주어집니다. ( $2 \le n \le 50\;000$ )

다음 줄에는 가중치 $c_i$ 의 목록이 주어집니다. ( $1 \le c_i \le 10\;000$ )

그다음 $n-1$ 줄에는 트리의 간선이 하나씩 주어집니다.

그다음 줄에는 $t_i$ 의 목록이 주어집니다.

마지막 줄에는 $k_i$ 의 목록이 주어집니다.

출력

$1 \le i \le n-1$ 에 대해 문제의 답을 한 줄에 하나씩 출력합니다.

문제 풀이

스포일러

일단 각 정점의 쌍의 LCA를 구할 필요가 있으므로, 각 정점의 depth를 구해 놓고 sparse table을 사용하여 LCA를 구합니다.

각 “쿼리"를 처리하는 방법 두 가지를 생각해 볼 수 있습니다.

각각의 $k$ 값에 대해, 모든 정점에서 루트 방향으로 $k$ 칸씩 점프하여 얻는 누적 합을 구해 놓고, 양쪽 노드에서 LCA까지의 간격 $k$ 의 합을 각각 두 개의 누적합의 차이로 구합니다.
나이브하게 $k$ 칸씩 루트 방향으로 점프해 가면서 방문하는 노드들의 가중치를 모두 더합니다.

둘 중 하나만 가지고는 이 문제를 풀 수 없지만 (각각 MLE와 TLE가 예상됨), 어떤 기준치 $X$ 를 기준으로 경우를 나눠서 둘을 섞는 방법을 고려해볼 수 있습니다.

$k \le X$ 이면 첫 번째 방법을 사용합니다. 이럴 경우 $nX$ 크기의 메모리가 추가로 필요하며, 쿼리당 $\mathcal{O}(\log n)$ 시간이 소요됩니다. (LCA 구하기, 두 경로에 대해 LCA의 조상 중에서 누적 합에서 뺄 값의 위치를 찾기)
$k > X$ 이면 두 번째 방법을 사용합니다. 이럴 경우 추가 메모리는 필요하지 않고, 쿼리당 $\mathcal{O}(\log n + \frac{n}{X} \log k)$ 시간이 소요됩니다. (LCA 구하기, $k$ 칸 점프를 방문 노드 개수만큼 반복)

메모리가 허용하는 한도 내에서 $\frac{n}{X}$ 를 최소화하는 것이 이득이므로 메모리 사용량을 계산해 보면, 64비트 정수 사용 시 $X = 1000$ 정도까지 허용됨을 알 수 있으며, 그렇게 구현하여 제출하면 약 1초 정도의 시간으로 통과됩니다.

누적 합을 사용하는 경우에서 LCA 정점이 더해져야 하는 경우에 주의합니다.

Last updated on 2025년 9월 24일 11:44:37

BOJ 18102 Есть ли делитель?BOJ 18591 Faraway