[백준BOJ] 3176_도로 네트워크 (C++)

https://www.acmicpc.net/problem/3176

3176번: 도로 네트워크

---

부모 테이블을 생성할 때에

같은 논리로

MAX 와 MIN 테이블을 만들어 주면 된다.

par[ i ][ k ] : i의 2^k번째 부모의 노드

MAX[ i ][ k ] : i의 2^k번쨰 부모까지의 최대값

MIN[ i ][ k ] : i의 2^k번쨰 부모까지의 최솟값

    for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
               MIN[j][i] = min(MIN[j][i - 1], MIN[par[j][i - 1]][i - 1]);
          }
     }

---

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define SWAP(a,b) {int t = b; b = a; a = t;}
#define MAX_N 100002

int depth[MAX_N];
int MAX[MAX_N][20];
int MIN[MAX_N][20];
int par[MAX_N][20];
bool visit[MAX_N];
vector<pair<int,int>> vec[MAX_N];

void dfs(int now,int prev, int prevDis, int prevDepth) {
     visit[now] = true;
     depth[now] = prevDepth;
     MAX[now][0] = prevDis;
     MIN[now][0] = prevDis;
     par[now][0] = prev;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               dfs(vec[now][i].first, now, vec[now][i].second, prevDepth + 1);
          }
     }
}

int lca(int x, int y) {
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}



int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N-1; i++) {
          int a, b, w; cin >> a >> b >> w;
          vec[a].push_back({ b,w });
          vec[b].push_back({ a,w });
     }
     dfs(1, 1, 0, 0);
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
               MIN[j][i] = min(MIN[j][i - 1], MIN[par[j][i - 1]][i - 1]);
          }
     }
     int M; cin >> M;
     for (int i = 0; i < M; i++) {
          int x, y; cin >> x >> y;
          int lca_node = lca(x, y);
          int x_to_lca = depth[x] - depth[lca_node];
          int y_to_lca = depth[y] - depth[lca_node];
          int maxAns = -1;
          int minAns = 1e9;
          for (int j = 19; j >= 0; j--) {
               if (x_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, MAX[x][j]);
                    minAns = min(minAns, MIN[x][j]);
                    x_to_lca -= (1 << j);
                    x = par[x][j];
               }
          }
          for (int j = 19; j >= 0; j--) {
               if (y_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, MAX[y][j]);
                    minAns = min(minAns, MIN[y][j]);
                    y_to_lca -= (1 << j);
                    y = par[y][j];
               }
          }
          cout << minAns << " " << maxAns << "\n";
     }
}