Tags

7 pages

Rooted Tree

[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

루트 C에서 시작하는 트리에서 "A 도시에 물 채우기"는 루트→A 경로의 각 정점 v에 깊이(v)+1 리터를 더합니다. 따라서 임의의 정점 v의 물의 양은 서브트리(v)에서 발생한 갱신 횟수 × (깊이(v)+1)로 환원됩니다. 오일러 투어로 트리를 평탄화하고 펜윅 트리(BIT)로 서브트리 구간의 갱신·질의를 처리해 O((N+Q)logN)에 해결합니다. 경계 입력과 64-bit 오버플로를 주의합니다.
[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

[Algorithm] cpp 백준 3319번: 전령들

트리의 각 도시에서 수도까지 메시지를 가장 빨리 전달하는 최소 시간을 구하는 문제입니다. 도시 i는 출발 준비 시간 S_i와 1km당 이동 시간 V_i를 가지며, 유일한 최단 경로를 따라 이동 중 중간 도시에서 다른 전령에게 넘길 수 있습니다. dp[u]를 루트까지의 거리 dist[u]를 이용해 dp[u] = S_u + V_u·dist[u] + min_{조상 x}(dp[x] − V_u·dist[x])로 정리하고, 조상 집합에 대한 직선 최소값 질의를 처리하기 위해 Li Chao Tree(선형함수 컨벡스 헐 트릭)를 트리 경로에 영속적으로 유지(퍼시스턴스)하여 각 정점에서 O(log C)에 답합니다. 64비트 정수 및 곱셈 시 128비트 캐스팅으로 오버플로를 방지합니다.
[Algorithm] cpp 백준 3319번: 전령들

[Algorithm] cpp-python 백준 18123번: 평행우주

각 별자리는 s≤30의 트리로 주어집니다. 위상(동형)만을 비교하므로 번호를 무시하고 트리 중심에서 AHU 문자열 정규형을 만들어 대표값을 구한 뒤, 두 중심일 땐 사전순 최소를 택해 중복을 제거합니다. 서로 다른 정규형의 개수가 한 우주에 공존 가능한 별자리 최대 수가 됩니다. 전체 별 수 합 ≤1e6 조건에서 선형에 가깝게 처리되어 안전합니다.
[Algorithm] cpp-python 백준 18123번: 평행우주

[Algorithm] C++ 백준 12736번 : Fireworks

백준 12736 Fireworks(APIO 2016)는 스위치-연결점-폭약으로 이루어진 트리에서 모든 폭약의 폭발 시각을 같게 만들기 위해 도화선 길이를 조정하는 최소 비용을 구하는 문제입니다. 볼록 함수(slope trick) 기반 트리 DP와 small-to-large 우선순위 큐 합병으로 O((N+M) log^2(N+M))에 해결합니다. 구현 핵심은 기울기 변화 지점을 우선순위 큐로 관리하고, 간선 통과 시 upperize 연산으로 기울기와 절편 변화를 반영하는 것입니다. 안전한 64-bit 정수 사용과 서브트리 크기 기준 정렬로 상수 시간을 줄여 AC를 얻습니다.
[Algorithm] C++ 백준 12736번 : Fireworks