정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다. www.acmicpc.net 1. 풀이 당연히 매번 루트를 재설정해가며 sparse table을 만들면 안 된다. 케이스 분류가 잘 안 돼서 구글링을 해봤는데 아래 링크가 가장 깔끔하게 정리해 둔 것 같다. https://cyberflower.github.io/2019/08..

0. 문제 주소 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B www.acmicpc.net 1. 풀이 N이 10만, 쿼리 개수가 10만이라 한 쿼리당 log N이 걸려야 한다. [PS/LCA] - [BOJ] ..

0. 문제 주소 https://www.acmicpc.net/problem/1626 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 *** 첫 다이아 문제 *** 기본 아이디어는 다음과 같다. 0. 크루스칼 알고리즘을 이용해 MST를 만든다. 기존 그래프와 별도로 만들어줄 것이고, 사용하지 않은 간선들은 notused_PQ(min heap)에 따로 ..