thisisuser's study

Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..

문제 링크https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판www.acmicpc.net 문제 선정 과정서브트리 전체의 값에 업데이트를 해야 하는데, 제한을 보니 이를 $logN$에 끝내야 하는 것으로 보였습니다.그냥 배열로도 단순히 풀면 나오지 않는 시간 복잡도인데 이를 트리에서 시행해야 한다는 점에서 꽤나 어려운 문제라 생각했습니다. 문제 풀이 전략문제를 모델링하면 다음과 같습니다.정점이 N개인 트리에 다음 두 가지 쿼리가 주어집니다..