(3176) 도로 네트워크

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

단계별로 풀어보기

47단계(최소 공통 조상) 4번째

 

 

 

트리 상에서 두 정점의 최단 경로는 LCA를 지나는 경로다. 이 경로 상에서 간선 가중치의 최대값과 최소값을 구해야 하므로 희소 테이블에서 해당 인덱스가 갖는 구간의 최대값과 최소값을 저장한다. 이후 LCA를 구하는 과정에서 희소 테이블을 이용해 정점을 점프할 때마다 최대값과 최소값을 갱신해준다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<int,int> p;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n;
  
  int h= (int)floor(log2(n))+1;
  vector adj(n+1, vector<p>()), dist(n+1, vector<p> (h));
  vector v(n+1, vector<int> (h));
  vector<int> depth(n+1);
  
  for(int i=1;i<n;i++){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj[a].push_back({c, b});
    adj[b].push_back({c, a});
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    depth[now]= depth[prev]+1;
    v[now][0]= prev;
    
    for(int i=1;i<h;i++){
      dist[now][i].first= min(dist[now][i-1].first, dist[v[now][i-1]][i-1].first);
      dist[now][i].second= max(dist[now][i-1].second, dist[v[now][i-1]][i-1].second);
      v[now][i]= v[v[now][i-1]][i-1];
    }
    
    for(p next:adj[now]){
      if(next.second==prev)  continue;
      
      dist[next.second][0].first= next.first;
      dist[next.second][0].second= next.first;
      self(self, next.second, now);
    }
  };
  
  dfs(dfs, 1, 0);
  
  auto lca= [&](int x, int y){
    p road= {1000001, 0};
    
    if(depth[x]<depth[y])  swap(x, y);
    
    for(int i=h-1;i>=0;i--){
      if(depth[v[x][i]]>=depth[y]){
        road.first= min(road.first, dist[x][i].first);
        road.second= max(road.second, dist[x][i].second);
        x= v[x][i];
      }
    }
    
    if(x==y)  return road;
    
    for(int i=h-1;i>=0;i--){
      if(v[x][i]!=v[y][i]){
        road.first= min({road.first, dist[x][i].first, dist[y][i].first});
        road.second= max({road.second, dist[x][i].second, dist[y][i].second});
        x= v[x][i];
        y= v[y][i];
      }
    }
    
    road.first= min({road.first, dist[x][0].first, dist[y][0].first});
    road.second= max({road.second, dist[x][0].second, dist[y][0].second});
    
    return road;
  };
  
  cin >> k;
  
  while(k--){
    int d, e;
    
    cin >> d >> e;
    
    p res= lca(d, e);
    
    cout << res.first << " " << res.second << "\n";
  }
  
  return 0;
}