Algorithm) SWEA 1855 영준이의 진짜 BFS c++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc&categoryId=AV5LnipaDvwDFAXc&categoryType=CODE&problemTitle=%EC%98%81%EC%A4%80%EC%9D%B4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

BFS+ LCA를 활용하는 문제였습니다

LCA를 활용해본 경험이 없어서 다시 공부해보고 문제를 풀었습니다 LCA 포스팅은 요기입니다

https://kuk6933.tistory.com/99

Algorithm) LCA(Lowest Common Ancestor) c++

LCA와 BFS만 아신다면 무난히 풀 수 있는 문제인듯 하네용

만약 오류가 뜨신다면 답 변수를 int로 선언하셨나 체크해보세요!

#include<iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MAX 100002

using namespace std;

int dp[MAX][20];
int depth[MAX];
long long ans;
int maxLevel;
vector<vector<int>> graph;

int LCA(int a, int b) {
    if(depth[a] != depth[b]) {
        if(depth[a] > depth[b]) { //b가 더 깊게
            swap(a, b);
        }

        for(int i= maxLevel; i>=0; i--) {
            if(depth[a] <= depth[dp[b][i]]) {
                b = dp[b][i];
            }
        }
    }

    int lca = a;
    if (a != b) {
        for(int i = maxLevel; i>=0; i--) {
            if(dp[a][i] != dp[b][i]) {
                a = dp[a][i];
                b = dp[b][i];
            }
            lca = dp[a][i];
        }
    }
    return lca;
}
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case) {
        int n;
        cin >> n;
        graph.clear();
        graph.resize(n+2);
        depth[1] = 0;
        ans = 0;
        maxLevel = (int)floor(log2(MAX));
        for (int i = 2; i <= n; i++) {
            int parent;
            cin >> parent;
            graph[parent].push_back(i);
            graph[i].push_back(parent);
            depth[i] = depth[parent] + 1;
            dp[i][0] = parent;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= maxLevel; j++) {
                int tmp = dp[i][j - 1];
                dp[i][j] = dp[tmp][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            sort(graph[i].begin(), graph[i].end());
        }

        queue<int> q;
        int pre = 1;
        q.push(1);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            int lca = LCA(cur, pre);
            int tm1 = depth[cur] - depth[lca];
            int tm2 = depth[pre] - depth[lca];
            ans += depth[cur] - depth[lca];
            ans += depth[pre] - depth[lca];
            pre = cur;
            for (int i = 0; i < graph[cur].size(); i++) {
                if (depth[graph[cur][i]] > depth[cur]) {
                    q.push(graph[cur][i]);
                }
            }
        }
        cout<<"#"<<test_case<<" "<<ans <<"\n";
    }
    return 0;
}