fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N=1e5+5,Log=23;
  5. int n,q,mx[N][Log],mn[N][Log],anc[N][Log],level[N],s[N];vector<pair<int,int>>adj[N];
  6. void BuildAncestors(int node,int parent,int cost)
  7. {
  8.     level[node]=level[parent]+1;
  9.     anc[node][0]=parent;
  10.     mx[node][0]=cost;
  11.     mn[node][0]=cost;
  12.     for(int o=1;o<Log;o++)
  13.     {
  14.         int p=anc[node][o-1];
  15.         anc[node][o]=anc[p][o-1];
  16.         mx[node][o]=max(mx[p][o-1],mx[node][o-1]);
  17.         mn[node][o]=min(mn[p][o-1],mn[node][o-1]);
  18.     }
  19.     for(auto it:adj[node])
  20.     {
  21.         if(it.first==parent)
  22.         {
  23.             continue;
  24.         }
  25.         BuildAncestors(it.first,node,it.second);
  26.     }
  27. }
  28. int KthAncestor(int node,int k)
  29. {
  30.     for(int o=Log-1;o>=0;o--)
  31.     {
  32.         if(k&(1<<o))
  33.         {
  34.             node=anc[node][o];
  35.         }
  36.     }
  37.     return node;
  38. }
  39. int MX(int node,int k)
  40. {
  41.     int ret=0;
  42.     for(int o=Log-1;o>=0;o--)
  43.     {
  44.         if(k&(1<<o))
  45.         {
  46.             ret=max(ret,mx[node][o]);
  47.             node=anc[node][o];
  48.         }
  49.     }
  50.     return ret;
  51. }
  52. int MN(int node,int k)
  53. {
  54.     int ret=n+5;
  55.     for(int o=Log-1;o>=0;o--)
  56.     {
  57.         if(k&(1<<o))
  58.         {
  59.             ret=min(ret,mn[node][o]);
  60.             node=anc[node][o];
  61.         }
  62.     }
  63.     return ret;
  64. }
  65. int LCA(int u,int v)
  66. {
  67.     if(level[u]<level[v])
  68.     {
  69.         swap(u,v);
  70.     }
  71.     u=KthAncestor(u,level[u]-level[v]);
  72.     if(u==v)
  73.     {
  74.         return u;
  75.     }
  76.     for(int i=Log-1;i>=0;i--)
  77.     {
  78.         if(anc[u][i]!=anc[v][i])
  79.         {
  80.             u=anc[u][i];
  81.             v=anc[v][i];
  82.         }
  83.     }
  84.     return anc[u][0];
  85. }
  86. void clear()
  87. {
  88.     for(int i=0;i<=n;i++)
  89.     {
  90.         adj[i].clear();
  91.         memset(anc[i],0,sizeof anc[i]);
  92.         memset(mx[i],0,sizeof mx[i]);
  93.         fill(mn[i],mn[i]+Log,n+5);
  94.     }
  95. }
  96. int getMx(int u,int v)
  97. {
  98.     int node=LCA(u,v);
  99.     return max(MX(u,level[u]-level[node]),MX(v,level[v]-level[node]));
  100. }
  101. int getMn(int u,int v)
  102. {
  103.     int node=LCA(u,v);
  104.     return min(MN(u,level[u]-level[node]),MN(v,level[v]-level[node]));
  105. }
  106. signed main()
  107. {
  108.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  109.     cin>>n>>q;
  110.     clear();
  111.     for(int i=1;i<n;i++)
  112.     {
  113.         int a,b;cin>>a>>b;
  114.         adj[a].push_back({b,i});
  115.         adj[b].push_back({a,i});
  116.     }
  117.     BuildAncestors(1,1,0);
  118.     while(q--)
  119.     {
  120.         int a,b;cin>>a>>b;
  121.         cout<<getMx(a,b)<<' '<<getMn(a,b)<<'\n';
  122.     }
  123.     return 0;
  124. }
Success #stdin #stdout 0.01s 11940KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/1mJI7z
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!