https://www.acmicpc.net/problem/32656
문제요약
- 트리가 주어짐(N=20만)
- LCA(a,b) = x가 주어짐
- 트리의 루트로 가능한 정점 후보의 개수 구하기
접근법
- LCA(a,b) = x 부분만 가지고 트리를 구성했을때, 나머지 루트가 가능한 것을 이어 붙이는 방식으로 접근해봄
- 일단 일부분만 구성한 트리는 a ---------- x --------- b 형태를 갖게 됨(x=a, x=b인 경우는 일단 제외)
- 이 상태에서 x에 "직접" 연결된 노드들은 모두 루트 노드가 될 수 있음
- x와 a 사이에 있는 노드는 제외(x와 b사이도 마찬가지)
- a 이후에 있는 노드도 제외(b이후에 있는 노드도 제외)
- x를 루트로 할 때 서브트리를 탐색함
- 서브트리에서 a나 b가 포함되어 있으면 무시
- 서브트리에서 a나 b가 포함되어 있지 않으면 서브트리의 모든 노드는 루트노드가 될 수 있음
- dfs 탐색을 하면서 서브트리의 크기를 구해나가는데
- a 또는 b를 만나면 크기를 0으로 처리
- 그렇지 않으면 크기를 구함
newbieski