📝 문제 정보#
🧐 관찰 및 접근#
- 도로가 N-1개인걸 보니 트리겠구만
- 이때 경로상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하라는데…
- HLD를 써도 되지만, sparse table에서의 RMQ처리처럼 진행해도 큰 문제가 없겠다.
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N;
rep(i, 0, N-1){
int u, v, w; cin >> u >> v >> w;
links[u].push_back({v, w});
links[v].push_back({u, w});
}
dfs(1, -1, 0);
rep(j, 1, 20) rep(i, 1, N+1) if(par[i][j-1]){
par[i][j] = par[par[i][j-1]][j-1];
mnDist[i][j] = min(mnDist[i][j-1], mnDist[par[i][j-1]][j-1]);
mxDist[i][j] = max(mxDist[i][j-1], mxDist[par[i][j-1]][j-1]);
}
int Q; cin >> Q;
while(Q--){
int u, v; cin >> u >> v;
auto [mn, mx] = calc(u, v);
cout << mn << ' ' << mx << '\n';
}
}