백준 8012 한동이는 영업사원!

문제 URL : https://www.acmicpc.net/problem/8012

8012번: 한동이는 영업사원!

 

문제 접근법 :  

 

두노드간의 거리문제입니다. 빠르게 구하기위해 

LCA의 depth를 이용하면되는데

두정점을 a,b라 할때

depth[a]+depth[b]-2*depth[lca(a,b)] 를 통해 쉽게 구할수있습니다.

 

소스코드 : 

//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
vector<int> v[30001],depth,iv;
int n, m;
int parent[17][30001];
void input(){
    cin>>n;
    int a,b;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin>>m;
    iv.resize(m);
    for(int i=0;i<m;i++)cin>>iv[i];
}
void dfs(int cur=1,int p=0,int h=0){
    parent[0][cur]=p;
    depth[cur]=h;
    for(int next:v[cur]){
        if(depth[next]==-1)dfs(next,cur,h+1);
    }
}
void sparseTable(){
    for(int i=1;i<=16;i++){
        for(int j=1;j<=n;j++){
            parent[i][j]=parent[i-1][parent[i-1][j]];
        }
    }
}
int lca(int x,int y){
    if(depth[x]>depth[y])swap(x,y);
    for(int i=16;i>=0;i--){
        if(depth[y]-depth[x]>=(1<<i)){
            y=parent[i][y];
        }
    }
    if(x==y)return x;
    for(int i=16;i>=0;i--){
        if(parent[i][x]!=parent[i][y]){
            x=parent[i][x];
            y=parent[i][y];
        }
    }
    return parent[0][x];
}
void solve(){
    depth=vector<int>(n+1,-1);
    dfs();
    sparseTable();
    long long sum=0;
    for(int i=1;i<m;i++){
        sum+=depth[iv[i]]+depth[iv[i-1]]-(2*depth[lca(iv[i],iv[i-1])]);
    }
    cout<<sum<<"\n"; 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.