fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define fi           first 
  4. #define si           second 
  5. #define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
  6. #define all(v)       v.begin(), v.end()
  7. #define Unique(v)    v.erase(unique(all(v)), v.end())   
  8. #define MASK(i)      (1LL << (i))
  9. #define bit(i,n)     (((n)>>(i)) & 1)
  10. #define Vii          vector<pair<int,int>>
  11. #define setpr(x)     cout<<setprecision(x)<<fixed
  12. #define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
  13. using namespace std;
  14.  
  15. const int Mod = 1E9 + 7;
  16. const long long INF  = 4E18;
  17. const int N = 2e5 + 1;
  18. const int Log = 18;
  19. int n,q;
  20. vector<int> g[N];
  21. int dp[N],dept[N],up[N][Log+2];
  22. vector<pair<int,int>> vec[N];
  23. void dfs_lca(int u, int p)
  24. {   
  25.     up[u][0] = p;
  26.     for(int i = 1; i <= Log; i++) up[u][i] = up[up[u][i-1]][i-1];
  27.     for(int v : g[u]) if(v != p)
  28.     {   
  29.         dept[v] = dept[u] + 1;
  30.         dfs_lca(v,u);
  31.     }
  32. }
  33. int LCA(int u, int v)
  34. {   
  35.     if(dept[u] < dept[v]) swap(u,v);
  36.     int LenK = dept[u] - dept[v];
  37.     for(int i = Log; i >= 0; i--) if(LenK&(1<<i)) u = up[u][i];
  38.     if(u == v) return u;
  39.     for(int i = Log; i >= 0; i--) if(up[u][i] != up[v][i])
  40.     {
  41.         u = up[u][i];
  42.         v = up[v][i];
  43.     }
  44.     return up[u][0];
  45. }
  46. int in[N],out[N],TimeDfs = 0;
  47. void dfs(int u, int p)
  48. {   
  49.     // in[u] = ++TimeDFS;
  50.     vec[u].push_back({0,u});
  51.     for(int v : g[u]) if(v != p)
  52.     {
  53.         dfs(v,u);
  54.     }
  55.     for(int v : g[u]) if(v !=p) vec[u].push_back({dp[v]+1,v});
  56.     sort(vec[u].begin(),vec[u].end(),greater<pair<int,int>>());
  57.     dp[u] = vec[u][0].fi;
  58.     // out[u] = ++TimeDFS;
  59. }
  60. void reroot(int u, int p)
  61. {
  62.     for(int v : g[u]) if(v != p)
  63.     {  // cout << u <<' ' << v << endl;
  64.         dp[u] = vec[u][0].first;
  65.         if(dp[v] + 1 == dp[u])
  66.         {
  67.             vec[v].push_back({vec[u][1].first + 1,u});
  68.         }
  69.         else 
  70.         {   
  71.             dp[v] = dp[u] + 1;
  72.             vec[v].push_back({dp[u]+1,u});
  73.         }
  74.         sort(vec[v].begin(),vec[v].end(),greater<pair<int,int>>());
  75.         reroot(v,u);
  76.     }
  77. }
  78. signed main(){
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);cout.tie(0);
  81.     //freopen("kein.inp","r",stdin)
  82.     //freopen("kein.out","w",stdout);
  83.     cin >> n >> q;
  84.     For(i,2,n)
  85.     {
  86.         int u,v;
  87.         cin >> u >> v;
  88.         g[u].push_back(v);
  89.         g[v].push_back(u);
  90.     }
  91.     dfs_lca(1,0);
  92.     dfs(1,0);
  93.     reroot(1,0);
  94.    // For(i,1,n) cout << vec[i][0].first <<' ' << vec[i][0].second <<  ' ' << vec[i][1].fi <<' ' << vec[i][1].si <<endl;
  95.    while(q--)
  96.    {
  97.         int u,v,node;
  98.         cin >> u >> v;
  99.         int anc = LCA(u,v);
  100.         int len = dept[u] + dept[v] - 2*dept[anc];
  101.         int k = (len+1)/2-1;
  102.       //  cout << u <<' ' << v <<' '<< k <<' ' << anc << '\n';
  103.         node = v;
  104.         if(dept[v]-dept[anc] >= k)
  105.         {
  106.             for(int i = 18; i >= 0; i--)if(k&(1<<i)) node = up[node][i];
  107.         }
  108.         else
  109.         {
  110.             k = len - k;
  111.             node = u;
  112.             for(int i = 18; i >= 0; i--)if(k&(1<<i)) node = up[node][i];
  113.         }
  114.        // cout <<"GG " << node << endl;
  115.         for(auto [Max,Node] : vec[node])
  116.         {   //cout << Max <<' ' << Node << endl;
  117.             int ancestor = LCA(node,Node)^LCA(u,node)^LCA(u,Node);
  118.            // cout << ancestor << endl;
  119.             if(ancestor == node) 
  120.             {   
  121.                // cout << Max << endl;
  122.                 cout << dept[node] + dept[u] - 2*dept[LCA(u,node)]+ Max <<'\n';
  123.                 break;
  124.             }
  125.         }
  126.    }
  127. }
Success #stdin #stdout 0.01s 17012KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/n3nHAD
language:
C++14 (gcc 8.3)
created:
1 day 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!