fork download
copy 
  1. #include <stdio.h>
  2. #include <map>
  3. #include <vector>
  4. #include <iostream>
  5. #include <cstring>
  6. using namespace std;
  7. #define pc(x) putchar_unlocked(x);
  8.     inline void writeInt (int n)
  9.     {
  10.         int N = n, rev, count = 0;
  11.         rev = N;
  12.         if (N == 0) { pc('0'); pc('\n'); return ;}
  13.         while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
  14.         rev = 0;
  15.         while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}  //store reverse of N in rev
  16.         while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
  17.         while (count--) pc('0');
  18.         pc('\n');
  19.     }
  20. vector<vector<int> > g ;
  21. map<int,int> mp ;
  22. int rmp[100001];
  23. int dp[100001][20] , val[100001] , depth[100001];
  24. int M ;
  25.  
  26. inline void fastRead_int(int *a)
  27. {
  28.     register char c=0;
  29.     while (c<33) c=getchar_unlocked();
  30.     *a=0;
  31.     while (c>33)
  32.     {
  33.         *a=*a*10+c-'0';
  34.         c=getchar_unlocked();
  35.     }
  36. }
  37.  
  38. struct node{
  39.     int sum  ;
  40.     node *left , *right ;
  41.     node(int s) {
  42.         sum =s;
  43.         left=this ;
  44.         right=this;
  45.     }
  46.     node(int s , node *l , node *r){
  47.         sum =s ;
  48.         left= l ;
  49.         right = r ;
  50.     }
  51. };
  52. node *EMPTY , *roots[100001];
  53.  
  54. node* insert(int val, node *n , int ns=1 , int ne=M-1){
  55.   //  cout<< ns << ' ' <<ne <<endl;
  56.     if(ns >val || ne< val ) return n ;
  57.     if(ns==ne) {
  58.         return new node(n->sum+1 , EMPTY , EMPTY);
  59.     }
  60.     node *l= insert(val,n->left,ns,(ns+ne)/2);
  61.     node *r= insert(val,n->right,(ns+ne)/2+1,ne);
  62.     return new node(l->sum+r->sum,l,r);
  63. }
  64.  
  65. void dfs(int u , int p){
  66.     depth[u]=depth[p]+1;//cout<< u <<' ' <<p << ' '<<val[u]<< endl;
  67.     roots[u]=insert(val[u],roots[p]);
  68.     for(int i = 0 ; i< g[u].size() ; i++){
  69.         int v= g[u][i];
  70.         if(v==p) continue;
  71.         dp[v][0]=u;
  72.         dfs(v,u);
  73.     }
  74. }
  75.  
  76. int lca(int a ,int b){
  77.     if(depth[a]<depth[b])swap(a,b);
  78.     int l = depth[a]-depth[b];
  79.     int d =  18 ;
  80.     for(int i = d ; i>=0 ; i--){
  81.         if((l>>i)&&1){
  82.             l-=(1<<i);
  83.             a=dp[a][i];
  84.         }
  85.     }
  86.     if(a==b)return a;
  87.     l=depth[a];
  88.     d =  18 ;
  89.     for(int i = d ; i>=0 ; i--){
  90.         if(dp[a][i]!=dp[b][i]) a=dp[a][i], b=dp[b][i];
  91.     }
  92.     return dp[a][0];
  93. }
  94.  
  95. int query(node *a , node*b  , node*c , node* d ,int k , int ns=1 , int ne=M-1){
  96.     if(ns==ne) return ns;
  97.     int cnt = a->left->sum+b->left->sum - c->left->sum - d->left->sum ;
  98.     if(cnt>=k) return query(a->left , b->left , c->left , d->left , k , ns, (ns+ne)/2);
  99.     return query(a->right , b->right , c->right , d->right ,k-cnt , (ns+ne)/2+1 , ne);
  100. }
  101.  
  102. int main()
  103. {
  104.  //   std::ios::sync_with_stdio(false);
  105.     int n , m ;
  106. //    scanf("%d%d",&n,&m);
  107.     fastRead_int(&n);fastRead_int(&m);
  108.     g.resize(n+1);
  109.     for(int i = 1 ; i<=n ; i++)fastRead_int(val+i),mp[val[i]]=0;
  110.     for(int i = 0 ; i<n-1 ; i++){
  111.         int a , b ;
  112.         fastRead_int(&a);fastRead_int(&b);
  113. //        scanf("%d%d",&a,&b);
  114.         g[a].push_back(b);
  115.         g[b].push_back(a);
  116.     }
  117.     M=1;
  118.     for(map<int,int>::iterator it=mp.begin() ;it!=mp.end() ; it++){
  119.         rmp[M]=it->first;
  120.         it->second=M++;
  121.     }
  122.     for(int i =1  ; i<=n ; i++){
  123.         val[i]=mp[val[i]];
  124.     }
  125.     EMPTY = new node(0);
  126.     roots[0]=EMPTY;
  127.    // memset(dp,-1 ,sizeof dp);
  128.     //cout<< M <<endl;
  129.     dfs(1 , 0);//cout<<"DSDS";
  130.     for(int i = 1 ; (1<<i)<=n ;i++){
  131.         for(int j = 1 ; j<=n ; j++){
  132.           //  if(dp[j][i-1]!=-1)
  133.             dp[j][i]=dp[dp[j][i-1]][i-1];
  134.         }
  135.     }
  136.     while(m--){
  137.         int a, b , k ;
  138. //        scanf("%d%d%d",&a,&b,&k);
  139.         fastRead_int(&a);fastRead_int(&b);fastRead_int(&k);
  140.         int c = lca(a,b);
  141.         int d = dp[c][0];
  142.      //   id(d==-1)d=0;
  143. //        printf("%d\n",rmp[query(roots[a],roots[b],roots[c],roots[d] , k)]);
  144.         printf("%d\n",rmp[query(roots[a],roots[b],roots[c],roots[d] , k)]);
  145.     }
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0s 12792KB
comments (?)
stdin
copy 
8 10
10500000 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 
1 1 1
2 3 2
2 3 3
4  8 2
3 7 2
stdout
copy 
2
8
9
10500000
7
10500000
9
10500000
7
9
https://ideone.com/dBmBJw
language:
C++14 (gcc 8.3)
created:
7 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!