Funcia
Lv.4heavy-light-decompositionsegment-treetree

경로 위 최고 점수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
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번 작업의 답을 순서대로 배열에 담아 반환하세요.

입출력 예

nedgesvaluesqueriesresult
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[]

제한 사항

  • 1≤1 \le n ≤200,000\le 200{,}000
  • edges.length == n −1- 1, edges[i] = [u, v], 0≤u,v<0 \le u, v < n, 산책로는 트리를 이룹니다.
  • −109≤-10^9 \le values[i], x ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000, 2번 작업이 적어도 하나 있습니다.

기대 복잡도

시간
O(N + Q log^2 N)
공간
O(N)

입출력 예

nedgesvaluesqueries기대 출력
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]

힌트

힌트

길을 한 칸씩 따라가면 질의마다 O(n)O(n)이고, 일자로 긴 트리에서는 너무 느립니다. 점수가 바뀌므로 미리 계산해 두는 방법도 쓸 수 없습니다.

Heavy-Light 분할(HLD)

트리를 몇 개의 사슬로 나눠, 어떤 경로든 O(log⁡n)O(\log n)개의 사슬 조각으로 쪼개지게 만듭니다.

  1. 아무 정점(예: 0)을 루트로 잡고 서브트리 크기를 구합니다.
  2. 각 정점에서 서브트리가 가장 큰 자식으로 가는 간선을 "무거운 간선"이라 하고, 무거운 간선을 이은 경로를 사슬로 삼습니다. 가벼운 간선을 하나 내려갈 때마다 서브트리 크기가 절반 이하로 줄어들므로, 루트에서 어느 정점까지 가벼운 간선은 O(log⁡n)O(\log n)개입니다.
  3. 사슬 하나가 연속된 번호를 갖도록 DFS 순서로 번호를 매기고, 그 순서로 최댓값 세그먼트 트리를 만듭니다.

질의 처리

  • 점수 변경: 세그먼트 트리의 한 점 갱신, O(log⁡n)O(\log n).
  • 경로 최댓값: u, v 중 사슬 머리가 더 깊은 쪽에서 "사슬 머리 ~ 현재 정점" 구간을 세그먼트 트리로 구하고 사슬 머리의 부모로 올라가기를, 두 정점이 같은 사슬에 올 때까지 반복합니다. 마지막으로 같은 사슬 안의 구간을 구합니다. O(log⁡2n)O(\log^2 n)입니다.

트리가 매우 깊을 수 있으므로 DFS는 반복문으로 구현하세요.

복잡도 목표

O(n+Qlog⁡2n)O(n + Q \log^2 n)입니다. 경로를 한 칸씩 걷는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)604 ms추정
C++ (GCC, gnu++23)604 ms도출됨
Python 3.133778 ms도출됨
Java 252768 ms도출됨
Kotlin 2.4 (JVM)2208 ms추정
C# 14 (.NET 10)2208 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.