peltorator

!HLD

Jul 7th, 2017
136
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fastRead ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  4. #define in(s) freopen(s, "r", stdin)
  5. #define out(s) freopen(s, "w", stdout)
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. const int MAXN = 200007, LOG = 21;
  12.  
  13. vector<int> h, g[MAXN], used, dp, down, p, in, out, intree, num, ind, upper;
  14.  
  15. vector<vector<int>> arr, tree;
  16.  
  17. int binup[MAXN][LOG];
  18.  
  19. int timer = 0;
  20.  
  21. void build(int i, int v, int l, int r)
  22. {
  23.     if (l == r)
  24.     {
  25.         tree[i][v] = arr[i][l - 1];
  26.         return;
  27.     }
  28.     int med = (r + l) / 2;
  29.     build(i, 2 * v, l, med);
  30.     build(i, 2 * v + 1, med + 1, r);
  31.     tree[i][v] = max(tree[i][2 * v], tree[i][2 * v + 1]);
  32. }
  33.  
  34. void upd(int i, int v, int l, int r, int q, int hi)
  35. {
  36.     if (r < l || q < l || q > r)
  37.         return;
  38.     if (r == l)
  39.     {
  40.         tree[i][v] = hi;
  41.         return;
  42.     }
  43.     int med = (r + l) / 2;
  44.     upd(i, 2 * v, l, med, q, hi);
  45.     upd(i, 2 * v + 1, med + 1, r, q, hi);
  46.     tree[i][v] = max(tree[i][2 * v], tree[i][2 * v + 1]);
  47. }
  48.  
  49. int f(int i, int v, int l, int r, int ql, int qr)
  50. {
  51.     if (r < l || ql > r || qr < l)
  52.         return -1e9;
  53.     if (ql <= l && r <= qr)
  54.         return tree[i][v];
  55.     int med = (r + l) / 2;
  56.     return max(f(i, 2 * v, l, med, ql, qr), f(i, 2 * v + 1, med + 1, r, ql, qr));
  57. }
  58.  
  59. int find_tree(int v, int pr)
  60. {
  61.     int ans = max(h[v], h[pr]);
  62.     while (v != pr)
  63.     {
  64.         if (num[v] == num[pr])
  65.         {
  66.             ans = max(ans, f(num[v], 1, 1, (int)arr[num[v]].size(), ind[pr], ind[v]));
  67.             v = pr;
  68.             continue;
  69.         }
  70.         ans = max(ans, f(num[v], 1, 1, (int)arr[num[v]].size(), 1, ind[v]));
  71.         v = p[upper[v]];
  72.     }
  73.     return ans;
  74. }
  75.  
  76. bool parent(int u, int p)
  77. {
  78.     return in[p] <= in[u] && out[u] <= out[p];
  79. }
  80.  
  81. int lca(int v, int u)
  82. {
  83.     for (int i = LOG - 1; i >= 0; i--)
  84.     {
  85.         if (!parent(u, binup[v][i]))
  86.             v = binup[v][i];
  87.     }
  88.     while (!parent(u, v))
  89.         v = p[v];
  90.     return v;
  91. }
  92.  
  93. int dfs(int v)
  94. {
  95.     in[v] = timer++;
  96.     used[v] = 1;
  97.     dp[v] = 1;
  98.     int maxx = 0, to = -1;
  99.     for (int i = 0; i < (int)g[v].size(); i++)
  100.     {
  101.         int u = g[v][i];
  102.         if (used[u])
  103.             continue;
  104.         int x = dfs(u);
  105.         dp[v] += x;
  106.         p[u] = v;
  107.         if (x > maxx)
  108.         {
  109.             maxx = x;
  110.             to = u;
  111.         }
  112.     }
  113.     down[v] = to;
  114.     out[v] = timer++;
  115.     return dp[v];
  116. }
  117.  
  118. void dfs1(int v)
  119. {
  120.     used[v] = 1;
  121.     if (!intree[v])
  122.     {
  123.         intree[v] = 1;
  124.         num[v] = (int)arr.size();
  125.         ind[v] = 1;
  126.         upper[v] = v;
  127.         arr.push_back(vector<int>(1, h[v]));
  128.     }
  129.     if (down[v] != -1)
  130.     {
  131.         int u = down[v];
  132.         intree[u] = 1;
  133.         num[u] = num[v];
  134.         ind[u] = ind[v] + 1;
  135.         upper[u] = upper[v];
  136.         arr[num[v]].push_back(h[u]);
  137.     }
  138.     for (int u : g[v])
  139.     {
  140.         if (used[u])
  141.             continue;
  142.         dfs1(u);
  143.     }
  144. }
  145.  
  146. int main()
  147. {
  148.     assert(in("mail.in"));
  149.     assert(out("mail.out"));
  150.     fastRead;
  151.     int n;
  152.     cin >> n;
  153.     h.resize(n + 1);
  154.     for (int i = 1; i <= n; i++)
  155.         cin >> h[i];
  156.     for (int i = 1; i < n; i++)
  157.     {
  158.         int u, v;
  159.         cin >> u >> v;
  160.         g[u].push_back(v);
  161.         g[v].push_back(u);
  162.     }
  163.     p.assign(n + 1, -1);
  164.     used.assign(n + 1, 0);
  165.     dp.assign(n + 1, 0);
  166.     down.assign(n + 1, -1);
  167.     in.assign(n + 1, 0);
  168.     out.assign(n + 1, 0);
  169.     p[1] = 1;
  170.     dfs(1);
  171.     for (int i = 1; i <= n; i++)
  172.         binup[i][0] = p[i];
  173.     for (int j = 1; j < LOG; j++)
  174.         for (int i = 1; i <= n; i++)
  175.             binup[i][j] = binup[binup[i][j - 1]][j - 1];
  176.     used.assign(n + 1, 0);
  177.     intree.assign(n + 1, 0);
  178.     num.assign(n + 1, 0);
  179.     upper.assign(n + 1, 0);
  180.     ind.assign(n + 1, 0);
  181.     dfs1(1);
  182.     for (int i = 0; i < (int)arr.size(); i++)
  183.     {
  184.         tree.push_back(vector<int>(5 * (int)arr[i].size() + 100, 0));
  185.         build(i, 1, 1, (int)arr[i].size());
  186.     }
  187.     int k;
  188.     cin >> k;
  189.     for (int i = 0; i < k; i++)
  190.     {
  191.         char c;
  192.         cin >> c;
  193.         if (c == '?')
  194.         {
  195.             int s, f;
  196.             cin >> s >> f;
  197.             int v = lca(s, f);
  198.             cout << max(find_tree(s, v), find_tree(f, v)) << "\n";
  199.         }
  200.         else
  201.         {
  202.             int v, hi;
  203.             cin >> v >> hi;
  204.             upd(num[v], 1, 1, (int)arr[num[v]].size(), ind[v], hi);
  205.             h[v] = hi;
  206.         }
  207.     }
  208.     return 0;
  209. }
RAW Paste Data