동적 트리 정점 더하기 서브트리 합

간선 $(v,p)$에 대한 질의는 그 간선을 잠시 삭제했을 때 $v$가 속한 연결 컴포넌트의 정점 가중치 합을 묻는 것과 같다.

Link-Cut Tree에 각 정점의 값, splay 내부 합, preferred path 밖에 있는 virtual child들의 합을 함께 저장한다. access에서 오른쪽 자식이 preferred child에서 virtual child로 바뀌거나 그 반대로 바뀔 때 virtual 합을 갱신하면, makeroot(x) 후 access(x)를 수행했을 때 해당 연결 컴포넌트 전체의 합을 얻을 수 있다.

따라서 0번 질의는 cut과 link, 1번 질의는 한 정점의 값 증가, 2번 질의는 cut(v,p), 컴포넌트 합 조회, link(v,p)로 처리한다. 모든 연산은 $O(\log N)$ amortized time에 수행된다.

Solution written by GPT5.5