백준(boj)6059 - Pasture Walking

문제 링크 - https://www.acmicpc.net/problem/6059

👀문제이해 및 풀이방법

가장 전형적인 트리 lca문제이다. 트리의 간선마다 길이가 있고 두 정점의 거리를 구하는 문제이다.
2차원 dis배열을 사용해서 두 정점간의 거리를 양방향 모두 입력해 둔다 이를 통해서 root를 1로 정해서 maketree를 통해 트리를 만들며 각 node마다 부모 node와 깊이, root와의 거리를 저장했다.
이후 두 정점의 depth를 통해 lca를 찾아 두 정점이 가진 root와의 거리의 합에서 lca의 root와의 거리*2를 빼주면 답이 나온다 처음에 *2를 안해서 틀렸었다.😥
트리 문제중 꼭 풀어봐야하는 문제중 하나라고 생각한다.

📝코드

#include <iostream>
#include <vector>
using namespace std;
struct _node{
    int parent;
    int depth;
    int dis;
};
class walking{
private:
    vector<_node> tree;
    vector<vector<int>> dis;
    int N,Q;
public:
    walking(){
        std::cin >> N >> Q;
        tree.resize(N+1,{0,0,});
        dis.resize(N+1,vector<int>(N+1,0));
        set_connect();
        maketree(1,0,1,0);
    }
    void set_connect(){
        int a,b,d;
        for(int i=1;i<N;i++){
            std::cin >>a >> b>> d;
            dis[a][b]=d;
            dis[b][a]=d;
        }
    }
    void maketree(int cur,int parent,int depth,int d){
        tree[cur].parent=parent;
        tree[cur].depth=depth;
        tree[cur].dis=d;
        for(int i=1;i<=N;i++)
            if(dis[cur][i] && i!=parent)
                maketree(i,cur,depth+1,d+dis[cur][i]);
    }
    int lca(int a,int b){
        int sol = tree[a].dis+tree[b].dis;
        if(tree[a].depth>tree[b].depth)
            swap(a,b);
        while(tree[a].depth!=tree[b].depth)
            b=tree[b].parent;
        if(a==b)
            return sol-tree[a].dis*2;
        while(a!=b){
            a=tree[a].parent;
            b=tree[b].parent;
        }
        return sol-tree[a].dis*2;
    }
    void find_sol(){
        int a,b;
        for(int i=0;i<Q;i++){
            std::cin >> a >> b;
            std::cout << lca(a,b) << '\n';   
        }
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    walking wk;
    wk.find_sol();
    return 0;
}