문제 링크 http://icpc.me/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 LCA(최소 공통 조상)를 구하여 풀 수 있다. root에서 a까지의 거리를 cost[a]라고 할 때, 트리에서 정점 a, b의 거리는 cost[a] + cost[b] - 2 * cost[lca]라고 할 수 있다. 코드 #include #include #include using namespace std; const int N = 4e4 + 4; vector v[N]; int dp[22][N], cost..

문제 링크 https://www.acmicpc.net/problem/13511 풀이 LCA를 이용하여 풀이할 수 있다. 백준 LCA2를 이해했다고 가정하고 설명하겠다. 1번 출력은 간단하다. dist[i]를 루트로부터 거리라고 할 때 dist[u] + dist[v] - 2*dist[LCA(u, v)]를 구하면 된다. 그림을 그려본다면 쉽게 이해할 수 있을 거다. 2번 출력은 u와 LCA사이에 있는 정점인지 v와 LCA사이에 있는 정점인지 판별한 후 부모 노드로 이동하면 된다. 코드 #include #include using namespace std; using ll = long long; using pll = pair; vector v[100005]; ll par[22][100005], lev[10000..

문제 링크 https://www.acmicpc.net/problem/3176 풀이 이 문제는 LCA를 이용한 문제이다. 쿼리당 O(logN)에 LCA를 처리하는 방법을 모른다면 LCA2부터 공부하는 것이 좋다. 이 글은 LCA2를 모두 이해했다고 가정하고 설명하겠다. 이 문제는 LCA를 구하는 과정에서 부분 최댓값과 최솟값을 O(1)에 구할 수 있어야 한다. 그러기 위해서는 sparse table을 이용하여 전처리를 해줘야 한다. 나는 여기와 여기를 보고 공부했다. 부분 최댓값과 최솟값을 구하는 전처리 코드는 아래와 같고 O(NlogN)에 처리할 수 있다. for (int j = 1; j = 0; i--) { if (lev[y] - lev[x] >= (1 = 0; i--) { if (par[x][i] !..

문제 링크 https://www.acmicpc.net/problem/3584 풀이 LCA(Lowest Common Ancestor) 기본 문제다. 최소 공통 조상은 트리에서 어떤 두 정점이 같은 가장 가까운 조상을 의미한다. 최소 공통 조상을 구하기 위해서 각 노드의 깊이를 저장해 놓는다. 그 후 a, b의 공통 조상을 찾는다고 한다면 a와 b의 깊이를 동일하게 맞춘 후 둘 다 한 칸씩 조상으로 이동하며 서로 같은지 확인하면 조상이 일치한 지 확인할 수 있다. 시간 복잡도는 O(depth)이다. cf) 이 문제는 단방향 그래프이므로 루트 노드를 따로 찾아줘야 한다. 코드 #include #include #include using namespace std; vector v[10004]; int par[10..