Lv.4heavy-light-decompositionsegment-treetree
경로 위 최고 점수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
캠핑장 n곳이 n-1개의 산책로로 이어져 있고, 어느 두 캠핑장 사이에도 길이 정확히 하나 있습니다(트리). 캠핑장 번호는 0부터 n-1까지이며, edges[i] = [u, v]는 u와 v를 잇는 산책로입니다. 캠핑장 i의 경치 점수는 values[i]입니다.
queries의 작업을 순서대로 처리합니다.
[1, u, x]— 캠핑장u의 점수를x로 바꿉니다.[2, u, v]—u에서v로 가는 길 위의 캠핑장(양 끝 포함) 중 가장 높은 점수를 구합니다.u = v일 수도 있습니다.
2번 작업의 답을 순서대로 배열에 담아 반환하세요.
입출력 예
| n | edges | values | queries | result |
|---|---|---|---|---|
5 | [[0, 1], [1, 2], [1, 3], [3, 4]] | [3, 1, 4, 1, 5] | [[2, 2, 4], [1, 4, 0], [2, 2, 4], [2, 0, 1], [1, 0, 9], [2, 3, 3]] | [5, 4, 3, 1] |
3 | [[2, 1], [1, 0]] | [-5, -7, -6] | [[2, 0, 2], [2, 1, 1], [1, 0, -8], [2, 2, 0]] | [-5, -7, -6] |
입출력 예 설명
예 1 — 2 → 1 → 3 → 4 경로의 점수는 4, 1, 1, 5라 처음 답은 5입니다. 4번 점수를 0으로 바꾸면 같은 경로의 최댓값은 4가 됩니다. 0 → 1은 3, 1이므로 3, 마지막 질의는 3번 하나뿐이라 1입니다(0번 변경은 영향이 없습니다).
예 2 — 점수는 음수일 수 있습니다. 0번 점수를 -8로 바꾼 뒤 2 → 1 → 0 경로의 최댓값은 -6입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, edges: int[][], values: int[], queries: int[][]) → int[]
제한 사항
-
n edges.lengthn,edges[i] = [u, v],n, 산책로는 트리를 이룹니다.-
values[i],x -
queries.length,2번 작업이 적어도 하나 있습니다.
기대 복잡도
- 시간
- O(N + Q log^2 N)
- 공간
- O(N)
입출력 예
| n | edges | values | queries | 기대 출력 |
|---|---|---|---|---|
5 | [[0,1],[1,2],[1,3],[3,4]] | [3,1,4,1,5] | [[2,2,4],[1,4,0],[2,2,4],[2,0,1],[1,0,9],[2,3,3]] | [5,4,3,1] |
3 | [[2,1],[1,0]] | [-5,-7,-6] | [[2,0,2],[2,1,1],[1,0,-8],[2,2,0]] | [-5,-7,-6] |
힌트
힌트
길을 한 칸씩 따라가면 질의마다 이고, 일자로 긴 트리에서는 너무 느립니다. 점수가 바뀌므로 미리 계산해 두는 방법도 쓸 수 없습니다.
Heavy-Light 분할(HLD)
트리를 몇 개의 사슬로 나눠, 어떤 경로든 개의 사슬 조각으로 쪼개지게 만듭니다.
- 아무 정점(예:
0)을 루트로 잡고 서브트리 크기를 구합니다. - 각 정점에서 서브트리가 가장 큰 자식으로 가는 간선을 "무거운 간선"이라 하고, 무거운 간선을 이은 경로를 사슬로 삼습니다. 가벼운 간선을 하나 내려갈 때마다 서브트리 크기가 절반 이하로 줄어들므로, 루트에서 어느 정점까지 가벼운 간선은 개입니다.
- 사슬 하나가 연속된 번호를 갖도록 DFS 순서로 번호를 매기고, 그 순서로 최댓값 세그먼트 트리를 만듭니다.
질의 처리
- 점수 변경: 세그먼트 트리의 한 점 갱신, .
- 경로 최댓값:
u,v중 사슬 머리가 더 깊은 쪽에서 "사슬 머리 ~ 현재 정점" 구간을 세그먼트 트리로 구하고 사슬 머리의 부모로 올라가기를, 두 정점이 같은 사슬에 올 때까지 반복합니다. 마지막으로 같은 사슬 안의 구간을 구합니다. 입니다.
트리가 매우 깊을 수 있으므로 DFS는 반복문으로 구현하세요.
복잡도 목표
입니다. 경로를 한 칸씩 걷는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 604 ms | 추정 |
| C++ (GCC, gnu++23) | 604 ms | 도출됨 |
| Python 3.13 | 3778 ms | 도출됨 |
| Java 25 | 2768 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 2208 ms | 추정 |
| C# 14 (.NET 10) | 2208 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |