lca
-
[백준] 13511번 트리와 쿼리 2문제 풀이 2020. 9. 2. 01:15
13511 트리와 쿼리 2 문제N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.아래의 두 쿼리를 수행하는 프로그램을 작성하시오* 1 u v: u에서 v로 가는 경로의 비용을 출력한다.* 2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다. 입력첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 간선의 비용 w가 주어진다.다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.다음 M개의 줄..
-
[백준] 17435번 합성함수와 쿼리문제 풀이 2020. 9. 1. 18:25
17435 합성함수와 쿼리 문제함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.* f1(x) = f(x)* fn+1(x) = f(fn(x))예를 들어 f4(1) = f(f(f(f(1))))이다.n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오. 입력첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m) 출력주어지는 ..
-
LCA알고리즘 2020. 8. 21. 18:36
LCA(Lowest Common Ancestor) - 개념: 트리에서 두 개의 정점를 선택하였을 때 최소 공통 조상(가장 가까운 공통 조상)을 찾는 알고리즘 - 구현방법 정점의 깊이를 저장하는 배열 depth[i] = i번 정점의 깊이 각 정점의 부모를 저장하는 배열 parent[i] = i번 정점의 부모 있다고 할때 1. 간단한 방법 : ① 두 정점 중 깊이가 더 깊은 정점를 찾아, 깊이가 같아질 때까지 그 정점의 부모로 계속 이동한다. ex) 정점 A, 정점 B if depth[A] > depth[B] // A정점이 깊이가 더 깊음 while(depth[A] != depth[B]) A = parent[A] ② 높이가 같아졌다면, 두 정점이 같아질 때까지 두 정점을 동시에 부모로 이동한다. while(..