fork download 
  1. /// vn.spoj.com/problems/LUBENICA/
  2.  
  3. /// hld+it by muoii
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 100007
  9. #define module 0
  10. #define long long long
  11. #define oo 1000000007
  12. #define loop(x) for(int ruuun=0;ruuun<x;ruuun++)
  13. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  14. int n,m;
  15. vector<int> tour,go;
  16. vector<int> id;
  17. vector<int> W;
  18. struct neigh{
  19.     int ver,wei;
  20. };
  21. vector< vector<neigh> > adj;
  22.  
  23. struct nodeTree{
  24.     int parent;
  25.     int depth;
  26.     int subsize;
  27.     int chainTop;
  28. };
  29. vector<nodeTree> infor;
  30. #define par(u) infor[u].parent
  31. #define depth(u) infor[u].depth
  32. #define subsize(u) infor[u].subsize
  33. #define chainTop(u) infor[u].chainTop
  34. #define jump(x) par(chainTop(x))
  35.  
  36. struct query{
  37.     int emi,ema;
  38. };
  39. struct it{
  40.     int n;
  41.     vector<int> qmin,qmax;
  42.     #define a(i) qmin[n+i-1]
  43.     #define b(i) qmax[n+i-1]
  44.     it() {};
  45.     it(const int &sz,const vector<int> &a){
  46.         n=sz;
  47.         qmin.resize(2*n+2); qmax.resize(2*n+2);
  48.         for(int i=1;i<=n;i++) a(i)=a[i],b(i)=a[i];
  49.         build();
  50.     }
  51.  
  52.     void build()
  53.     {
  54.         for(int i=n-1;i>=1;i--)
  55.             qmin[i]=min(qmin[i<<1],qmin[i<<1|1]),
  56.             qmax[i]=max(qmax[i<<1],qmax[i<<1|1]);
  57.     }
  58.  
  59.     query get(int l,int r)
  60.     {
  61.         int emi=+oo,ema=-oo;
  62.         for(l+=n-1,r+=n;l<r;l>>=1,r>>=1)
  63.         {
  64.             if(l&1) emi=min(emi,qmin[l]),ema=max(ema,qmax[l]),l++;
  65.             if(r&1) --r,emi=min(emi,qmin[r]),ema=max(ema,qmax[r]);
  66.         }
  67.         return {emi,ema};
  68.     }
  69. } st;
  70.  
  71. void data()
  72. {
  73.     adj.resize(n+1);
  74.     infor.resize(n+1);
  75.     W.resize(n+1);
  76.     id.resize(n+1);
  77.     tour.resize(1);
  78. }
  79.  
  80. ///--------------
  81. void dfs(const int &u,const int &parent,const int &depth)
  82. {
  83.     infor[u]={parent,depth,1};
  84.  
  85.     for(const auto &nei: adj[u])
  86.         if(nei.ver!=parent)
  87.             W[nei.ver]=nei.wei,dfs(nei.ver,u,depth+1),subsize(u)+=subsize(nei.ver);
  88. }
  89.  
  90. void hld(const int &u,const int &parent,const int &top)
  91. {
  92.     id[u]=tour.size();
  93.     tour.push_back(W[u]);
  94.     go.push_back(u);
  95.     chainTop(u)=top;
  96.  
  97.     int special=0;
  98.     for(const auto &nei: adj[u])
  99.         special=(nei.ver!=parent && subsize(nei.ver)>subsize(special))?nei.ver:special;
  100.  
  101.     if(special==0) return;
  102.  
  103.     hld(special,u,top);
  104.  
  105.     for(const auto &nei: adj[u])
  106.         if(nei.ver!=parent && nei.ver!=special)
  107.             hld(nei.ver,u,nei.ver);
  108. }
  109.  
  110. void lca(int x,int y)
  111. {
  112.     query get;
  113.     int emi=+oo,ema=-oo;
  114.     while(chainTop(x)!=chainTop(y))
  115.     if(depth(chainTop(x))>depth(chainTop(y)))
  116.         {
  117.             get=st.get(id[chainTop(x)],id[x]);
  118.             emi=min(emi,get.emi);
  119.             ema=max(ema,get.ema);
  120.  
  121.             x=jump(x);
  122.         }
  123.     else
  124.         {
  125.             get=st.get(id[chainTop(y)],id[y]);
  126.             emi=min(emi,get.emi);
  127.             ema=max(ema,get.ema);
  128.  
  129.             y=jump(y);
  130.         }
  131.  
  132.     get=(depth(x)<depth(y))?st.get(id[x]+1,id[y]):st.get(id[y]+1,id[x]);
  133.  
  134.     emi=min(emi,get.emi);
  135.     ema=max(ema,get.ema);
  136.  
  137.     cout<<emi<<" "<<ema<<"\n";
  138.     return;
  139. }
  140.  
  141. int main()
  142. {
  143. 	#ifdef dmdd
  144.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  145.     #endif // dmdd
  146.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  147.  
  148.     cin>>n;
  149.     data();
  150.  
  151.     int u,v,w;
  152.     loop(n-1) cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});
  153.  
  154.     ///tree&lcawithhld:
  155.     dfs(1,0,1);
  156.     hld(1,0,1);
  157.     st=it(n,tour);
  158.  
  159.     cin>>m;
  160.     while(m-->0) cin>>u>>v,lca(u,v);
  161.     return 0;
  162. }
  163.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3
stdout 
1 2
2 4
1 5
2 2
1 4
https://ideone.com/3UbAxV
language:
C++14 (gcc 8.3)
created:
6 years 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!