Toolofv 님의 블로그

문제N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연..

문제N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 문제해결방법 - (서칭 참조) 그 전의 빌드업 문제를 풀어보았어도, 희소배열을 적용하는 개념이 이해하기가 어려웠다. 아무 참조없이 이대로..