알고리즘 일지
20030 - 트리와 쿼리 17 본문
풀이 1
f[x] 를 x노드의 문제에 지정된 수식값이라고 하자.
특정 노드에 i에, A[i]++
연산이 추가되면, 모든 노드 j에 대해,
f[j] += dist(j, i) 이다.
이 연산…. 서브트리에 날릴 수 있다.
그 위로는? 방법이 보이지 않는다…
풀이 2
그럼 A[i]를 직접 헤비라잇과 오일러투어로 합쳐만들고, 연산 시켜준다.
Weighted centroid라는 정점이 이때, 답이 되게 되는데, 그 이유는 최대한 가중치들의 가운데에 있는 정점이 경로가 겹치는 것을 피할 수 있기 때문이다.
이거 어케구하는지 모른다;;