BOJ1761: 정점들의 거리 작성일 2020-04-28 https://www.acmicpc.net/problem/1761 LCA와 루트로부터의 거리를 응용하는 문제. LCA는 일단 손에 익는것 같다 큰 무리 없었음 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h> using namespace std; const int D = 20, MN = 40010; int N; int par[D+1][MN]; int dist[MN]; int depth[MN]; vector<pair<int,int>> adj[MN]; void dfs(int u, int p, int d, int dep) { if (depth[u]) return; dist[u] = d; depth[u] = dep; par[0][u] = p; for(auto [v, di]: adj[u]) dfs(v, u, d + di, dep+1); } void fillParent() { for(int i = 1; i < D; i++) for(int j = 1; j <= N; j++) par[i][j] = par[i-1][par[i-1][j]]; } int findLCA(int a, int b) { if(depth[a] > depth[b]) swap(a,b); if (a == b) return a; for(int i = D; i >= 0; i--) if((1 << i) <= depth[b] - depth[a]) b = par[i][b]; if (a == b) return a; for(int i = D; i >= 0; i--) if(par[i][a] != par[i][b]) a = par[i][a], b = par[i][b]; return par[0][a]; } int main() { scanf("%d", &N); for(int i = 0; i < N-1; i++) { int u, v, d; scanf("%d %d %d", &u, &v, &d); adj[u].push_back({v,d}); adj[v].push_back({u,d}); } dfs(1, 0, 0, 1); fillParent(); int Q, a, b; scanf("%d", &Q); for(int i = 0; i < Q; i++) { scanf("%d %d", &a, &b); int lca = findLCA(a,b); int ans = dist[a] + dist[b] - dist[lca] * 2; printf("%d\n", ans); } }