트리 병합을 이용한 최대 비용 계산 알고리즘
문제 정의
노드 개수가 \\(n\\)개인 트리가 주어집니다. 각 노드 \\(i\\)에는 두 정수값 \\(a_i\\)와 \\(b_i\\)가 할당되어 있습니다. 노드 선택 순서는 다음 조건을 만족해야 합니다: 어떤 노드를 선택하기 전에 그 노드의 모든 조상 노드가 먼저 선택되어야 합니다. 이러한 순서로 선택된 노드 배열 \\(p\\)에 대해 비용은 다음 식으로 계산됩니다:
\[\sum_{i=1}^n \lef ...
5월 23일 06:28에 게시됨
그래프 알고리즘의 응용: 연결성 관리와 조상 찾기
최근 두 가지 그래프 관련 문제를 접하게 되었는데, 각각 복잡한 구조를 다루는 데 있어 유사한 접근 방식을 사용하고 있어 정리해보았다.
AcWing 2069. 네트워크 분석
태그: 병합-찾기 집합, 동적 연결성 관리
이 문제는 초기에 간선이 없는 (n)개의 노드로 구성된 네트워크에서 시작한다. 두 가지 유형의 연산이 주어진다:
두 노드 (a)와 (b)를 연결한다.
노드 (p)에 값 ...
5월 23일 02:50에 게시됨