백준 5916번 - 농장 관리
https://www.acmicpc.net/problem/5916 5916번: 농장 관리 첫째 줄에 농장의 수 N과 쿼리의 수 M(1 ≤ N, M ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 도로가 연결하는 농장의 번호가 주어진다. 다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net HLD 풀이가 정해이지만 LCA + 세그트리로 해결할 수 있습니다. 필요한 배경지식 최소 공통 조상(LCA) 세그먼트 트리 오일러 투어 테크닉 문제 해결 방법 우선 N개의 노드와 N-1개의 간선이 존재하므로 농장은 트리 형태의 자료구조를 가진다는것을 확인할 수 있습니다. 이 문제에서 조심해야 할 부분으로는 P와 Q쿼리 모두 노드가 아닌 간선의 값을 처리해야 하기 때문에 모든 간..
알고리즘 공부/문제풀이
2021. 5. 28. 06:11
반응형