https://www.acmicpc.net/problem/12746 12746번: Traffic (Large) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 철로를 지난 사람의 수를 구할 수 있습니다. 농장 관리 문제와 다른점은 업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다. ..
https://www.acmicpc.net/problem/11960 11960번: Max Flow Farmer John has installed a new system of \(N-1\) pipes to transport milk between the \(N\) stalls in his barn (\(2 \leq N \leq 50,000\)), conveniently numbered \(1 \ldots N\). Each pipe connects a pair of stalls, and all stalls are connected to each-other www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 ..
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쿼리 모두 노드가 아닌 간선의 값을 처리해야 하기 때문에 모든 간..