https://www.acmicpc.net/problem/25402
문제요약
- 트리가 주어짐(N = 25만). 쿼리가 주어짐(Q = 10만)
- 쿼리마다 노드가 주어지고(S), S에 속하는 정점만을 이용하여 이동이 가능한 순서쌍의 개수 구하기(쿼리로 주어진 모든 노드 개수의 합 = 100만)
- => 서브트리들의 크기를 구해서 합/곱으로 순서쌍을 구하는 문제
접근법
- 처음에는 안 쓰이는 점을 기준으로 쪼개고, 곱하고로 시도했는데 잘 안됨
- 쿼리로 주어진 모든 노드 개수의 합 = 100만에서 힌트를 얻어서 서브 트리마다 union-find 연산을 해도 시간내에 들어오겠다고 생각
- set을 이용해서 쓰여지는 노드 -> 안쓰여지는 노드 -> 안쓰여지는 간선 -> 쓰여지는 간선을 추출하고, 쓰여지는 간선으로 union-find를 시도하였으나 시간 초과
- 쓰여지는 간선은 100만개이겠지만, 안쓰여지는 노드가 O(N)이라 시간초과
- 쓰여지는 간선만 빠르게 찾으면 좋겠다!!
쓰여지는 간선만 찾기
- 간선을 인접리스트로 안하고 단일 "한개" 로만 표현이 가능하지 않나
- 어짜피 트리이고, 간선의 개수는 N - 1일테니, 노드 하나당 간선 하나를 부여하면, 나중에 사용한 노드를 알고 있을때 사용한 간선을 자연스럽게 얻지 않을까
- (a, b) 가 주어지면 a에 할당하거나, 이미 할당되어있으면 b에 할당
- 잘 돌아가는 듯 보였으나 실패
- a - b - c - d 처럼 되었을때, [b] = a, [c] = d로 할당을 해버리면, (b, c) 간선을 바르게 할당 할 수 없음
- 결국 임시 인접리스트를 만들고, DFS를 수행하고, 자식노드가 부모노드를 바라보게 함
- => 결국 자식-부모 관계로 간선을 구선하는 방식이었음!
- 노드 하나당 간선 하나를 매핑 완료한 상태에서
- 쓰여지는 노드를 순회하면서 해당 노드에 있는 간선을 확인
- 간선이 없더라도 쓰여진 다른 노드를 통해 간선을 사용할 것임. 그래도 없으면 진짜 없는 것이고
- 간선의 양쪽 노드가 모두 쓰여지는 노드이면 union-find 수행
- 모두 끝내고 나서 그룹을 확인 -> 크기 확인 -> 순서쌍 개수 확인
- 그리고 사용한 노드에 대해서만 변수 초기화수행 : 1 ~ N에 대해서 수행하면 안됨
- 어려웠음
newbieski