αλγριθμο

문제 www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 LCA(Lowest Common Ancestor)를 사용합니다. 먼저, 다음 4개의 배열을 만듭니다: \(graph[i][j].x,\ graph[i][j].y:\) \(i\)의 \(j\)번째 자식 노드와 그 노드까지의 거리. \(par[i][j]:\) \(i\)의 \(2^j\)번째 조상. \(depth[i]:\) \(i\)의 깊이. \(dist[i]:\) 루트로부터 \(i\)까지의 거리. 트..

문제 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 LCA(Lowest Common Ancestor)를 사용합니다. 사실 이번 문제는 전에 풀었던 11438 - LCA 2문제와 거의 다를 것이 없습니다. 다만, 다른 점이라면 루트노드가 따로 주어지지 않기 때문에 직접 찾아야한다는 것입니다. 하지만 그건 어렵지 않습니다. ​ 먼저, 각 테스트케이스별 간선들의 정보를 입력받은 다음 노드 하나를 무작위로 ..

문제 www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 문제 제목 그대로 LCA(Lowest Common Ancestor)를 사용합니다. 각 노드의 자식 정보를 담은 배열 \(graph\)와 각 노드의 조상 정보를 담은 배열 \(par\), 그리고 각 노드의 깊이를 담은 배열 \(depth\)가 있을 때 주어진 트리를 순회하면서 다음 작업을 수행합니다. 현재 노드를 \(i\)라고 할 때: \(par[i][j]\)에 \(i\)의 \(2^j\)번째 ..