fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int ROOT = 0;
  5. int VAL[250007];
  6. int subtreesize[250007];
  7. vector<vector<int>> GRAF(250007);
  8. vector<int> UPEDGE(250007);
  9. vector<bool> UPHEAVY(250007);
  10. vector<bool> HASDOWN(250007);
  11. vector<int> HEAVYSTART;
  12. vector<vector<int>> HEAVYPATHS;
  13. vector<pair<int, int>> HEAVYPATH(250007);
  14. int preorder[250007];
  15. int postorder[250007];
  16. int jump[250007][20];
  17. const int base = (1<<18);
  18. int MAXSEGMENTTREE[2*base+7];
  19. int MINSEGMENTTREE[2*base+7];
  20. int prelicz = 0;
  21.  
  22. void USTAW(int A, int K){
  23.     A+=base;
  24.     MAXSEGMENTTREE[A]=K;
  25.     MINSEGMENTTREE[A]=K;
  26.     A/=2;
  27.     while(A != 0){
  28.         MAXSEGMENTTREE[A]=max(MAXSEGMENTTREE[A*2], MAXSEGMENTTREE[A*2+1]);
  29.         MINSEGMENTTREE[A]=min(MINSEGMENTTREE[A*2], MINSEGMENTTREE[A*2+1]);
  30.         A/=2;
  31.     }
  32. }
  33. int MAXONINTERVAL(int A, int B){
  34.     A--;
  35.     B++;
  36.     A+=base;
  37.     B+=base;
  38.     int wyn = -1e9-6;
  39.     while(A/2 != B/2){
  40.         if(A%2 == 0){
  41.             wyn = max(wyn, MAXSEGMENTTREE[A+1]);
  42.         }
  43.         if(B%2 == 1){
  44.             wyn = max(wyn, MAXSEGMENTTREE[B-1]);
  45.         }
  46.         A/=2;
  47.         B/=2;
  48.     }
  49.     return wyn;
  50. }
  51. int MINONINTERVAL(int A, int B){
  52.     A--;
  53.     B++;
  54.     A+=base;
  55.     B+=base;
  56.     int wyn = 1e9+6;
  57.     while(A/2 != B/2){
  58.         if(A%2 == 0){
  59.             wyn = min(wyn, MINSEGMENTTREE[A+1]);
  60.         }
  61.         if(B%2 == 1){
  62.             wyn = min(wyn, MINSEGMENTTREE[B-1]);
  63.         }
  64.         A/=2;
  65.         B/=2;
  66.     }
  67.     return wyn;
  68. }
  69.  
  70.  
  71. int licz = 1;
  72. int DFS(int NODE, pair<int, bool> prevedge){
  73.     preorder[NODE]=prelicz;
  74.     prelicz++;
  75.     jump[NODE][0]=prevedge.first;
  76.     UPEDGE[NODE]=prevedge.first;
  77.     UPHEAVY[NODE]=prevedge.second;
  78.     int SIZE = 0;
  79.     for(auto i : GRAF[NODE]){
  80.         if(i != UPEDGE[NODE]){
  81.             SIZE+=DFS(i, {NODE, 0});
  82.         }
  83.     }
  84.     SIZE++;
  85.     subtreesize[NODE]=SIZE;
  86.     for(auto i : GRAF[NODE]){
  87.         if(i != UPEDGE[NODE]){
  88.             if(subtreesize[i] >= (SIZE+1)/2){
  89.                 UPHEAVY[i]=true;
  90.                 HASDOWN[NODE]=true;
  91.             }
  92.         }
  93.     }
  94.     if(!HASDOWN[NODE]){
  95.         HEAVYSTART.push_back(NODE);
  96.     }
  97.     postorder[NODE]=prelicz;
  98.     prelicz++;
  99.     return SIZE;
  100. }
  101.  
  102. bool insubtree(int A, int B){
  103.     if(preorder[A] <= preorder[B] && postorder[A] >= postorder[B])return true;
  104.     return false;
  105. }
  106. int LCA(int A, int B){
  107.     if(insubtree(A, B)){
  108.         return A;
  109.     }
  110.     else if(insubtree(B, A)){
  111.         return B;
  112.     }
  113.     for(int i = 19; i >= 0; --i){
  114.         if(!insubtree(jump[A][i], B)){
  115.             A = jump[A][i];
  116.         }
  117.     }
  118.     return jump[A][0];
  119. }
  120.  
  121. int MAXOFPATH(int A, int GOAL){
  122.    // cerr << "Calculating MAX on path: " << A << " " << GOAL << "\n";
  123.     if(HEAVYPATH[A].first == HEAVYPATH[GOAL].first){
  124.        // cerr << "ON SAME HEAVY PATH, returning " << MAXONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[GOAL].second) << "\n";
  125.         return MAXONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[GOAL].second);
  126.     }
  127.     int LAST = HEAVYPATHS[HEAVYPATH[A].first].back();
  128.    // cerr << "NOT ON SAME HEAVY PATH, returning MAXOF " << MAXONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[LAST].second) << " and " << jump[LAST][0] << " " << GOAL << "\n";
  129.     return max(MAXONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[LAST].second), MAXOFPATH(jump[LAST][0], GOAL));
  130. }
  131.  
  132. int MINOFPATH(int A, int GOAL){
  133.     if(HEAVYPATH[A].first == HEAVYPATH[GOAL].first){
  134.         return MINONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[GOAL].second);
  135.     }
  136.     int LAST = HEAVYPATHS[HEAVYPATH[A].first].back();
  137.     return min(MINONINTERVAL(HEAVYPATH[A].second, HEAVYPATH[LAST].second), MINOFPATH(jump[LAST][0], GOAL));
  138. }
  139. int main(){
  140.     ios_base::sync_with_stdio(0); cin.tie(0);
  141.     int N, Q; cin >> N >> Q;
  142.     for(int i = 0; i < 2*base+7; ++i){   
  143.         MAXSEGMENTTREE[i]=-1e9-6;
  144.         MINSEGMENTTREE[i]=1e9+6;
  145.     }
  146.     for(int i = 0; i < N; ++i){
  147.         cin >> VAL[i];
  148.     }
  149.     for(int i = 0; i < N-1; ++i){   
  150.         int a, b; cin >> a >> b;
  151.         GRAF[a].push_back(b);
  152.         GRAF[b].push_back(a);
  153.     }
  154.     DFS(0, {-1, 0});
  155.     for(int i : HEAVYSTART){
  156.         HEAVYPATHS.push_back({i});
  157.         HEAVYPATH[i]={HEAVYPATHS.size()-1, licz};
  158.         licz++;
  159.         int idx = i;
  160.         USTAW(licz-1, VAL[idx]);
  161.         while(UPHEAVY[idx] == 1){
  162.             idx = UPEDGE[idx];
  163.             HEAVYPATHS[HEAVYPATHS.size()-1].push_back({idx});
  164.             HEAVYPATH[idx]={HEAVYPATHS.size()-1, licz};
  165.             USTAW(licz, VAL[idx]);
  166.             licz++;
  167.         }
  168.     }
  169.     jump[0][0]=0;
  170.     for(int i = 1; i <= N; ++i){
  171.         for(int j = 1; j < 20; ++j){
  172.             jump[i][j]=jump[jump[i][j-1]][j-1];
  173.         }
  174.     }
  175.     while(Q--){
  176.         int A, B; cin >> A >> B;
  177.         int lca = LCA(A, B);
  178.         cout << max(MAXOFPATH(A, lca), MAXOFPATH(B, lca))-min(MINOFPATH(B, lca), MINOFPATH(A, lca)) << "\n";
  179.     }
  180. }
Success #stdin #stdout 0.01s 19176KB
comments (?)
stdin
copy 
7 1
5 4 2 4 3 -1 -5
0 1
1 3
1 6
2 4
2 6
5 6
5 4
stdout
copy 
8
https://ideone.com/AX1RSu
language:
C++ (gcc 8.3)
created:
7 days 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!