fork download
copy 
  1. /// pst+lca by muoii
  2.  
  3. /// www.spoj.com/problems/COT/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 100007
  9. #define oo 1000000007
  10. #define mid ((l+r)>>1)
  11. #define meset(a,x) memset(a,x,sizeof(a))
  12. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  13. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  14. struct pst{
  15.     int cnt;
  16.     pst *left,*right;
  17.  
  18.     pst(): cnt(0), left(this), right(this) {};
  19.  
  20.     pst(const int &c,pst *l,pst *r): cnt(c), left(l), right(r) {};
  21.  
  22.     pst* insert(const int &l,const int &r,const int &add,const int &val = 1)
  23.     {
  24.         if(add<l || add>r) return this;
  25.  
  26.         if(l==r) return new pst(cnt+val,0,0);
  27.  
  28.         return new pst(cnt+val,left->insert(l,mid,add,val),right->insert(mid+1,r,add,val));
  29.     }
  30. } *null=new pst();
  31. struct nodeTree{
  32.     pst *root;
  33.     int anc[22];
  34.     int depth;
  35. };
  36.  
  37. int n,m;
  38. int maxa;
  39. vector<int> a;
  40. map<int,int> mark;
  41. vector<int> realval;
  42. vector<vector<int>> adj;
  43. vector<nodeTree> infor;
  44. #define root(u) infor[u].root
  45. #define par(u) infor[u].anc[0]
  46. #define ances(u,i) infor[u].anc[i]
  47. #define depth(u) infor[u].depth
  48.  
  49. void data()
  50. {
  51.     a.resize(n+1);
  52.     adj.resize(n+1);
  53.     realval.resize(n+1);
  54.     infor.resize(n+1);
  55.     root(0)=null;
  56. }
  57.  
  58. void dfs(const int &u,const int &parent,const int &depth)
  59. {
  60.     root(u)=root(parent)->insert(1,maxa,mark[a[u]]);
  61.     par(u)=parent;
  62.     depth(u)=depth(parent)+1;
  63.  
  64.     for(int i=1;1<<i<n;i++) ances(u,i)=ances(ances(u,i-1),i-1);
  65.  
  66.     for(const int &v: adj[u])
  67.         if(v!=parent)
  68.             dfs(v,u,depth+1);
  69. }
  70.  
  71. int lca(int x,int y)
  72. {
  73.     if(depth(x)<depth(y)) swap(x,y);
  74.  
  75.     while(depth(x)>depth(y)) x=ances(x,(int)log2(depth(x)-depth(y)));
  76.  
  77.     int lg=log2(depth(x));
  78.  
  79.     while(x!=y)
  80.     {
  81.         while(lg>0 && ances(x,lg)==ances(y,lg)) --lg;
  82.         x=ances(x,lg),y=ances(y,lg);
  83.     }
  84.  
  85.     return x;
  86. }
  87.  
  88. int query(pst *u,pst *v,pst *par,pst *grand,const int &k,const int &l,const int &r)
  89. {
  90.     if(l==r) return l;
  91.  
  92.     int cnt=u->left->cnt + v->left->cnt - par->left->cnt - grand->left->cnt;
  93.  
  94.     return (cnt>=k)?query(u->left,v->left,par->left,grand->left,k,l,mid):query(u->right,v->right,par->right,grand->right,k-cnt,mid+1,r);
  95. }
  96.  
  97. int main()
  98. {
  99.     #ifdef dmdd
  100.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  101.     #endif //dmdd
  102.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  103.  
  104.     cin>>n>>m;
  105.     data();
  106.     for(int i=1;i<=n;i++) cin>>a[i],mark[a[i]];
  107.  
  108.     maxa=0;
  109.     for(auto &pii: mark) ++maxa,pii.second=maxa,realval[maxa]=pii.first;
  110.  
  111.     int u,v,k,lcanc;;
  112.  
  113.     loop(n-1) cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);
  114.  
  115.     dfs(1,0,1);
  116.  
  117.     loop(m) cin>>u>>v>>k,lcanc=lca(u,v),cout<<realval[query(root(u),root(v),root(lcanc),root(par(lcanc)),k,1,maxa)]<<"\n";
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
stdout
copy 
2
8
9
105
7
https://ideone.com/gB6Pts
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!