fork download
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int N,M;
  5. int depth[100001];
  6. vector<int> node[100001];
  7. int parent[100001][21];
  8.  
  9. void dfs(int x,int par){
  10. depth[x]=depth[par]+1;
  11. for(int nxt:node[x]){
  12. if(nxt==par) continue;
  13. parent[nxt][0]=x;
  14. dfs(nxt,x);
  15. }
  16. }
  17. int lca(int a,int b){
  18. if(depth[a]>depth[b]) swap(a,b);
  19. for(int i=20;i>=0;i--){
  20. if(depth[b]-depth[a]>=(1<<i)) b=parent[b][i];
  21. } //같은 깊이로 맞춰주기
  22. if(a==b) return a;
  23. for(int i=20;i>=0;i--){
  24. if(parent[a][i]!=parent[b][i]){
  25. a=parent[a][i];
  26. b=parent[b][i];
  27. }
  28. }
  29. return parent[a][0];
  30. }
  31. int main() {
  32. ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  33. cin>>N;
  34. for(int i=1,u,v;i<N;i++){
  35. cin>>u>>v;
  36. node[u].push_back(v);
  37. node[v].push_back(u);
  38. }
  39. dfs(1,0);
  40. for(int i=1;i<21;i++)
  41. for(int j=1;j<=N;j++)
  42. parent[j][i]=parent[parent[j][i-1]][i-1];
  43. cin>>M;
  44. while(M--){
  45. int a,b;
  46. cin>>a>>b;
  47. cout<<lca(a,b)<<'\n';
  48. }
  49. return 0;
  50. }
Success #stdin #stdout 0.01s 7732KB
stdin
7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
3
1 6
1 4
2 6
stdout
0
0