값이 바뀌는 트리 경로의 최대 신호

자바스크립트 코딩테스트 문제로 heavy-light-decomposition 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard heavy-light-decomposition 함수명: maxRouteSignalWithUpdates 제한 시간: 700ms

트리의 노드 값이 계속 바뀔 때, 두 노드 사이 경로에서 가장 큰 신호 값을 빠르게 구하는 문제입니다.

문제 설명

0번부터 n - 1번까지 번호가 붙은 노드가 있습니다.

edges는 트리의 간선 목록이며, 각 원소는 [a, b] 형태입니다. signals[i]는 i번 노드의 현재 신호 값입니다.

operations에는 두 종류의 작업이 섞여 있습니다.

["update", node, value]: node번 노드의 신호 값을 value로 바꿉니다.
["query", a, b]: a번 노드에서 b번 노드까지의 경로에 포함된 노드 중 가장 큰 신호 값을 구합니다.

모든 query 작업의 결과를 순서대로 배열에 담아 반환하는 maxRouteSignalWithUpdates 함수를 작성하세요.

제한사항

1 <= n <= 100000
edges.length === n - 1
edges[i] = [a, b]
0 <= a, b < n
입력으로 주어지는 간선은 항상 하나의 트리를 이룹니다.
signals.length === n
-1000000000 <= signals[i] <= 1000000000
1 <= operations.length <= 100000
operations[i]는 ["update", node, value] 또는 ["query", a, b]입니다.
0 <= node, a, b < n
-1000000000 <= value <= 1000000000
반환값은 각 query 결과를 입력 순서대로 담은 배열입니다.
모든 노드 값이 음수일 수 있습니다.

예시

입력:
- n = 5
- edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
- signals = [5, 1, 7, 3, 9]
- operations = [["query", 2, 4], ["update", 1, 10], ["query", 0, 2], ["update", 4, 0], ["query", 4, 3]] -> 출력: [9, 10, 3]
입력:
- n = 1
- edges = []
- signals = [-4]
- operations = [["query", 0, 0], ["update", 0, 6], ["query", 0, 0]] -> 출력: [-4, 6]
입력:
- n = 6
- edges = [[0, 1], [1, 2], [1, 3], [3, 4], [3, 5]]
- signals = [2, 8, 1, 4, 6, 3]
- operations = [["query", 2, 5], ["update", 1, -5], ["query", 2, 5], ["update", 5, 10], ["query", 4, 5], ["query", 0, 2]] -> 출력: [8, 4, 10, 2]

힌트

트리에서 두 노드 사이 경로를 매번 직접 따라가면 최악의 경우 한 질의가 O(n)이 됩니다.
Heavy-Light Decomposition은 트리 경로를 몇 개의 연속 구간 질의로 바꾸는 기법입니다.
노드 값을 DFS 순서로 펼친 배열 위에 세그먼트 트리를 만들면, 점 갱신과 구간 최댓값 질의를 빠르게 처리할 수 있습니다.

해설

이 문제는 경로 질의와 값 갱신이 함께 들어오기 때문에 단순 DFS나 부모 포인터만으로는 부족합니다.

핵심은 트리를 Heavy-Light Decomposition으로 펼치는 것입니다.

먼저 각 노드의 부모, 깊이, 서브트리 크기를 구합니다. 그리고 각 노드에서 서브트리 크기가 가장 큰 자식을 heavy child로 고릅니다. 이렇게 고른 heavy edge를 따라 이어지는 노드들은 하나의 chain이 됩니다.

그다음 각 chain을 위에서 아래로 방문하며 노드에 새로운 위치 번호를 붙입니다. 같은 chain에 속한 노드들은 펼친 배열에서도 연속한 구간이 됩니다. 따라서 한 chain 안의 경로 최댓값은 세그먼트 트리의 구간 최댓값 질의 한 번으로 구할 수 있습니다.

두 노드 a, b의 경로를 질의할 때는 두 노드가 같은 chain에 들어올 때까지 반복합니다.

head[a]와 head[b]가 다르면 더 깊은 head를 가진 쪽을 위로 올립니다.
올리는 동안 head[x]부터 x까지의 펼친 배열 구간 최댓값을 답 후보에 반영합니다.
두 노드가 같은 chain에 들어오면, 더 얕은 노드부터 더 깊은 노드까지의 마지막 구간을 조회합니다.

update 작업은 훨씬 단순합니다. 바뀐 노드의 펼친 배열 위치를 찾아 세그먼트 트리에서 해당 한 칸만 새 값으로 갱신하면 됩니다.

경로 하나는 HLD에서 최대 O(log n)개의 chain 구간으로 쪼개지고, 각 구간 최댓값 조회와 점 갱신은 세그먼트 트리에서 O(log n)에 처리됩니다. 따라서 전체 시간 복잡도는 대략 O((n + operations.length) log^2 n)이며, 구현 방식에 따라 경로 질의의 로그 하나를 더 줄일 수도 있습니다.

초기 답을 0으로 두면 모든 값이 음수인 테스트에서 틀립니다. 최댓값의 초기값은 충분히 작은 값, 예를 들어 -Infinity로 두어야 합니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과