BOJ 8012, 한동이는 영업사원!
ProblemSolving ·기본 LCA 알고리즘을 사용하는 문제이다.
풀이
1번 도시부터 출발하여 주어진 순서대로 도시들을 지나가면서 총 거리를 출력하는 문제이다. 현재 도시의 거리와 이동할 도시의 거리를 더해주고 최소공통조상의 거리를 빼주면 된다!
(거리는 1번 도시에서 n번 도시로 가는 거리로 잡았다. 거리는 항상 1이므로 depth배열을 이용하였다.)
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<functional>
using namespace std;
vector<vector<int>> v(40001);
int depth[40001];
int par[40001][20];
int sum, p, a = 1;
void dfs(int now, int level)
{
depth[now] = level;
for (int i = 0; i < v[now].size(); i++)
{
int next = v[now][i];
if (depth[next]) continue;
dfs(next, level + 1);
par[next][0] = now;
}
}
int LCA(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
int dif = depth[a] - depth[b];
for (int i = 0; i <= 16; i++)
if (dif & (1 << i))
a = par[a][i];
if (a != b)
{
for (int i = 16; i >= 0; i--)
if (par[a][i] && par[a][i] != par[b][i])
{
a = par[a][i];
b = par[b][i];
}
a = par[a][0];
}
return a;
}
int main()
{
int n, m;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d %d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 1);
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= n; j++)
par[j][i] = par[par[j][i - 1]][i - 1];
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
sum += depth[a];
int b = a;
scanf("%d", &a);
sum += depth[a];
sum -= 2 * depth[LCA(a, b)];
}
printf("%d\n", sum);
return 0;
}