fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define noSuccess t--
  3. #define int long long
  4. #define pb push_back 
  5. #define F first	
  6. #define S second
  7. #define Sattar_is_the_best ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8. #define all(s) s.begin(),s.end()
  9. #define yes "YES\n"
  10. #define no "NO\n"
  11. #define sz size
  12.  
  13. using namespace std;
  14. const int maxn = 100300;
  15. const int mod = 1e9 + 7;
  16. int n;
  17. int c[maxn],a[maxn],pos,dist[maxn];
  18. int tin[maxn],tout[maxn],timer;
  19. vector<pair<int,int>>g[maxn];
  20. void dfs(int v,int pr){
  21.   tin[v]=++timer;
  22.   a[++pos]=v;
  23.   for(auto [to,w] : g[v]){
  24.     if(to==pr) continue;
  25.     c[to]=c[v]+1;
  26.     dfs(to,v);
  27.     a[++pos]=v;
  28.   }
  29.   tout[v]=++timer;
  30. }
  31. pair<int,int> p[maxn],mn[maxn][40];
  32. int lg[maxn];
  33. void build(){
  34.   for(int i=2;i<=n*2;i++){
  35.     lg[i]=lg[i/2]+1;
  36.   }
  37.   for(int k=1;k<=20;k++){
  38.     for(int i=1;i+(1<<k)-1<=2*n;i++){
  39.       mn[i][k]=min(mn[i][k-1],mn[i+(1<<(k-1))][k-1]);
  40.     }
  41.   }
  42. }
  43. int up(int a,int b){
  44.   if(tin[a]<=tin[b] && tout[a]>=tout[b]) return a;
  45.   if(tin[b]<=tin[a] && tout[b]>=tout[a]) return b;
  46.   return -1;
  47. }
  48. int lca(int a,int b){
  49.   if(up(a,b)!=-1) return up(a,b); 
  50.   int l=tout[a],r=tin[b];
  51.   if(l>r) l=tout[b],r=tin[a];
  52.   int k=lg[r-l+1];
  53.   auto ans=min(mn[l][k],mn[r-(1<<k)+1][k]);
  54.   return ans.S;
  55. }
  56. void tryAgain(){
  57.   cin>>n;
  58.   for(int i=1;i<=n-1;i++){
  59.     int u,v,w;
  60.     cin>>u>>v>>w;
  61.     g[u].pb({v,w});
  62.     g[v].pb({u,w});
  63.   }
  64.   dfs(1,1);
  65.   for(int i=1;i<=2*n;i++){
  66.     mn[i][0]={c[a[i]],a[i]};
  67.   }
  68.   build();
  69.   int q;
  70.   cin>>q;
  71.   while(q--){
  72.     int a,b;
  73.     cin>>a>>b;
  74.     cout<<lca(a,b)<<'\n';
  75.   }
  76. }
  77. signed main(){
  78.   Sattar_is_the_best
  79.   // freopen("length.in", "r", stdin);
  80.   // freopen("length.out", "w", stdout);
  81.   int t = 1;
  82.   // cin >> t;
  83.   while(noSuccess){
  84.     tryAgain();
  85.   }
  86. }
Success #stdin #stdout 0.01s 7788KB
comments (?)
stdin
copy 
3
2 1 1
3 1 1
3
1 2
1 3
2 3
stdout
copy 
1
1
1
https://ideone.com/AF9wAW
1
1
1
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!