https://www.acmicpc.net/problem/20931
문제요약
- 트리에서 두 가지의 명령을 수행
- 혹 붙이기 : 연산을 통해 얻은 노드에 새로운 노드 추가 + 간선 가중치
- 찾기 : 특정 노드에서 길이가 l인 곳의 노드 찾기(l이하에 걸쳐 있는 노드로 생각하면 됨)
접근법
- lca에서 사용한 sparse 테이블 사용
- 1, 2, 4, 8, ... 부모가 누구인지
- 1, 2, 4, 8, ... 거리가 얼마인지
- l인 곳 노드 찾기
- 1, 2, 4, 8, ... 거리를 보면서 l이하인 가장 높은 노드를 찾음
- 시간 복잡도
newbieski