Advertisement
Guest User

Untitled

a guest
May 20th, 2018
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <signal.h>
  4. #include <stdio.h>
  5. #include <unistd.h>
  6. #include <cstring>
  7. #define pb push_back
  8. using namespace std;
  9.  
  10. const int N = 50001;
  11.  
  12. vector<int> g[N], lca[N];
  13.  
  14. vector<vector<int> > hld;
  15.  
  16. int tin[N], tout[N], sz[N], val[N];
  17. pair<int,int> inds[N];
  18.  
  19. int n, m;
  20. int timer = 0;
  21. int l = 1;
  22.  
  23. void dfs_hld(int v, int vec=0, int p=0) {
  24.     hld[vec].push_back(v);
  25.     if (g[v].size() == 1 && v != 0 || n == 1) {
  26.        
  27.         return;
  28.     }
  29.  
  30.     int maxi = -1;
  31.     for (int i = 0; i < g[v].size(); ++i) {
  32.         if (g[v][i] != p && (sz[g[v][i]] > sz[g[v][maxi]] || maxi == -1))
  33.             maxi = i;
  34.     }
  35.     for (int i = 0; i < g[v].size(); ++i) {
  36.         if (g[v][i] == p) continue;
  37.         if (i == maxi) {
  38.             dfs_hld(g[v][i], vec, v);
  39.         }
  40.         else {
  41.             hld.push_back(vector<int>());
  42.             dfs_hld(g[v][i], hld.size()-1, v);
  43.         }
  44.     }
  45. }
  46.  
  47. int dfs(int v, int p=0) {
  48.     lca[v][0] = p;
  49.     tin[v] = timer++;
  50.     sz[v] = 1;
  51.     for (int i = 1; i <= l; ++i) {
  52.         lca[v][i] = lca[lca[v][i-1]][i-1];
  53.     }
  54.     for (int to : g[v]) {
  55.         if (to != p)
  56.             sz[v] += dfs(to, v);
  57.     }
  58.     tout[v] = timer++;
  59.     return sz[v];
  60. }
  61.  
  62. bool isparent(int v, int u) {
  63.     return tin[v] <= tin[u] && tout[v] >= tout[u];
  64. }
  65.  
  66. int get_lca(int v, int u) {
  67.     if (isparent(v, u)) return v;
  68.     if (isparent(u, v)) return u;
  69.     for (int i = l; i --> 0;) {
  70.         // cout << lca[v][i] << endl;
  71.         if (!isparent(lca[v][i], u))
  72.             v = lca[v][i];
  73.     }
  74.     return lca[v][0];
  75. }
  76.  
  77. void init() {
  78.     while ((1<<l) <= n) ++l;
  79.     for (int i = 0; i < n; ++i) {
  80.         lca[i] = vector<int>(l+1);
  81.     }
  82. }
  83.  
  84. class ST {
  85. private:
  86.     vector<int> a, t;
  87.     int n;
  88. public:
  89.     ST(){}
  90.     ST(vector<int> v) : a(v) {
  91.         n = v.size();
  92.         t.assign(4*n+10, 0);
  93.         build(1, 0, n-1);
  94.     }
  95.     void build(int v, int tl, int tr) {
  96.         if (tl == tr)
  97.             t[v] = a[tl];
  98.         else {
  99.             int tm = (tl + tr) >> 1;
  100.             build(v*2, tl, tm);
  101.             build(v*2+1, tm+1, tr);
  102.             t[v] = max(t[v*2], t[v*2+1]);
  103.         }
  104.     }
  105.  
  106.     int get_max(int v, int tl, int tr, int l, int r) {
  107.         if (l > r)
  108.             return -1;
  109.         if (tl == l && tr == r)
  110.             return t[v];
  111.         int tm = (tl + tr) >> 1;
  112.         return max(get_max(v*2, tl, tm, l, min(r, tm)),
  113.                    get_max(v*2+1, tm+1, tr, max(l, tm+1), r));
  114.     }
  115.  
  116.     void modify(int v, int tl, int tr, int pos, int val) {
  117.         if (tl == tr)
  118.             t[v] = val;
  119.         else {
  120.             int tm = (tl + tr) >> 1;
  121.             if (pos <= tm)
  122.                 modify(v*2, tl, tm, pos, val);
  123.             else
  124.                 modify(v*2+1, tm+1, tr, pos, val);
  125.             t[v] = max(t[v*2], t[v*2+1]);
  126.         }
  127.     }
  128.     int get_size() {
  129.         return n;
  130.     }
  131. };
  132.  
  133. vector<ST*> forest;
  134.  
  135. int get_ans(int a, int b) {
  136.     int p = get_lca(a, b);
  137.     // solve for [a, p]
  138.     int pind = inds[p].first;
  139.     int amax = -1, bmax = -1;
  140.     while (inds[a].first != pind) {
  141.         amax = max(amax, forest[inds[a].first]->get_max(
  142.             1, 0, forest[inds[a].first]->get_size()-1, 0, inds[a].second));
  143.         a = lca[hld[inds[a].first][0]][0];
  144.     }
  145.     amax = max(amax, forest[inds[a].first]->get_max(
  146.             1, 0, forest[inds[a].first]->get_size()-1, inds[p].second, inds[a].second));
  147.  
  148.     // solve for [b, p]
  149.     while (inds[b].first != pind) {
  150.         bmax = max(bmax, forest[inds[b].first]->get_max(
  151.             1, 0, forest[inds[b].first]->get_size()-1, 0, inds[b].second));
  152.         b = lca[hld[inds[b].first][0]][0];
  153.     }
  154.     bmax = max(bmax, forest[inds[b].first]->get_max(
  155.             1, 0, forest[inds[b].first]->get_size()-1, inds[p].second, inds[b].second));
  156.     int ans = max(amax, bmax);
  157.     return ans;
  158. }
  159.  
  160. void update(int v, int val) {
  161.     forest[inds[v].first]->modify(1, 0, forest[inds[v].first]->get_size()-1, inds[v].second, val);
  162. }
  163.  
  164. void segfault_sigaction(int signal, siginfo_t *si, void *arg) {
  165.     while (1) {};
  166. }
  167.  
  168. int32_t main() {
  169.     ios_base::sync_with_stdio(0);
  170.     cin.tie(0);
  171.     cout.tie(0);
  172.     struct sigaction sa;
  173.  
  174.     memset(&sa, 0, sizeof(struct sigaction));
  175.     sigemptyset(&sa.sa_mask);
  176.     sa.sa_sigaction = segfault_sigaction;
  177.     sa.sa_flags   = SA_SIGINFO;
  178.  
  179.     sigaction(SIGSEGV, &sa, NULL);
  180.     cin >> n;
  181.     for (int i = 0; i < n; ++i) {
  182.         cin >> val[i];
  183.     }
  184.     for (int i = 0; i < n-1; ++i) {
  185.         int a, b;
  186.         cin >> a >> b;
  187.         --a, --b;
  188.         g[a].pb(b);
  189.         g[b].pb(a);
  190.     }
  191.  
  192.     init();
  193.     dfs(0);
  194.  
  195.     hld.push_back(vector<int>());
  196.     try {
  197.     dfs_hld(0);
  198.     } catch(...) {while(1){}}
  199.    
  200.     for (int i = 0; i < hld.size(); ++i) {
  201.         vector<int> vev;
  202.         for (int j = 0; j < hld[i].size(); ++j) {
  203.             vev.push_back(val[hld[i][j]]);
  204.         }
  205.         forest.push_back(new ST(vev));
  206.         for (int j = 0; j < hld[i].size(); ++j) {
  207.             int p = hld[i][j];
  208.             inds[p] = {i, j};
  209.             // cout << p << " ";
  210.         }
  211.         // cout << endl;
  212.     }
  213.     int q;
  214.     cin >> q;
  215.     for (int i = 0; i < q; ++i) {
  216.         char c;
  217.         cin >> c;
  218.         int a, b;
  219.         cin >> a >> b;
  220.         if (c == '?') {
  221.             --a, --b;
  222.             cout << get_ans(a, b) << endl;
  223.         }
  224.         else {
  225.             --a;
  226.             update(a, b);
  227.         }
  228.     }
  229.     return 0;
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement