HoBoCTb

Untitled

Aug 6th, 2021
753
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *  author: 2lasy2code
  3.  *  created: 16.03.2021 15:42:12
  4.  *  task: Link
  5. **/
  6.  
  7. #include <bits/stdc++.h>
  8. #define ioBoost ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  9. using namespace std;
  10. #define int long long
  11.  
  12. #define all(x) (x).begin(), (x).end()
  13. #define rep(i, l, r) for(int i = l; i < r; ++i)
  14.  
  15. class node {
  16. public:
  17.     int val, res, id, d;
  18.     node *l = nullptr, *r = nullptr, *p = nullptr;
  19.     bool rev = false;
  20.     int sz = 1;
  21.  
  22.     explicit node(int _id, int _val) : id(_id), val(_val), res(_val), d(0) {}
  23.  
  24.     void pull() {
  25.         sz = 1;
  26.         res = val + d;
  27.  
  28.         if (l != nullptr) {
  29.             l->p = this;
  30.             sz += l->sz;
  31.             res = max(res, (l->res + l->d));
  32.         }
  33.  
  34.         if (r != nullptr) {
  35.             r->p = this;
  36.             sz += r->sz;
  37.             res = max(res, (r->res + r->d));
  38.         }
  39.     }
  40.  
  41.     void push() {
  42.         if (rev) {
  43.             if (l != nullptr)
  44.                 l->rev ^= 1;
  45.             if (r != nullptr)
  46.                 r->rev ^= 1;
  47.             swap(l, r);
  48.             rev = false;
  49.         }
  50.         val += d;
  51.         res += d;
  52.         if (l != nullptr)
  53.             l->d += d;
  54.         if (r != nullptr)
  55.             r->d += d;
  56.         d = 0;
  57.     }
  58. };
  59.  
  60. bool is_bst_root(node *v) {
  61.     if (v == nullptr)
  62.         return false;
  63.     v->push();
  64.     return (v->p == nullptr || (v->p->l != v && v->p->r != v));
  65. }
  66.  
  67. void rotate(node *v) {
  68.     node *u = v->p;
  69.     u->push(), v->push();
  70.     v->p = u->p;
  71.     if (v->p != nullptr) {
  72.         if (v->p->l == u)
  73.             v->p->l = v;
  74.         if (v->p->r == u)
  75.             v->p->r = v;
  76.     }
  77.     if (v == u->l)
  78.         u->l = v->r, v->r = u;
  79.     else
  80.         u->r = v->l, v->l = u;
  81.     u->pull(), v->pull();
  82. }
  83.  
  84. void splay(node *v) {
  85.     if (v == nullptr)
  86.         return;
  87.     while (!is_bst_root(v)) {
  88.         node *u = v->p;
  89.         if (!is_bst_root(u)) {
  90.             if ((u->l == v) ^ (u->p->l == u)) {
  91.                 rotate(v);
  92.             } else {
  93.                 rotate(u);
  94.             }
  95.         }
  96.         rotate(v);
  97.     }
  98.     v->push();
  99. }
  100.  
  101. int get_size(node *v) {
  102.     splay(v);
  103.     return (v != nullptr ? v->sz : 0);
  104. }
  105.  
  106. int get_res(node *v) {
  107.     splay(v);
  108.     return (v != nullptr ? v->res + v->d : 0);
  109. }
  110.  
  111. node *expose(node *v) {
  112.     if (v == nullptr) return nullptr;
  113.  
  114.     node *c = nullptr;
  115.     for (auto u = v; u != nullptr; u = u->p) {
  116.         splay(u);
  117.         u->r = c;
  118.         u->pull();
  119.         c = u;
  120.     }
  121.  
  122.     splay(v);
  123.     return c;
  124. }
  125.  
  126. void evert(node *&v) {
  127.     expose(v);
  128.     v->rev ^= 1;
  129. }
  130.  
  131. node *root(node *v) {
  132.     expose(v);
  133.     while (v->l) {
  134.         v = v->l;
  135.         v->push();
  136.     }
  137.     expose(v);
  138.  
  139.     return v;
  140. }
  141.  
  142. node *parent(node *v) {
  143.     expose(v);
  144.  
  145.     if (v->l == nullptr)
  146.         return nullptr;
  147.     v = v->l;
  148.     v->push();
  149.     while (v->r) {
  150.         v = v->r;
  151.         v->push();
  152.     }
  153.     return v;
  154. }
  155.  
  156. bool path(node *v, node *u) {
  157.     if (v == u) return true;
  158.  
  159.     expose(u), expose(v);
  160.     return u->p != nullptr;
  161. }
  162.  
  163. void link(node *v, node *u) {
  164.     if (path(v, u)) return;
  165.  
  166.     evert(v);
  167.     v->p = u;
  168. }
  169.  
  170. void cut(node *v) {
  171.     expose(v);
  172.     if (v->l == nullptr)
  173.         return;
  174.     v->l->p = nullptr;
  175.     v->l = nullptr;
  176. }
  177.  
  178. node *lca(node *v, node *u) {
  179.     if (!path(v, u))
  180.         return nullptr;
  181.     expose(v);
  182.     return expose(u);
  183. }
  184.  
  185. int depth(node *v) {
  186.     expose(v);
  187.     return get_size(v->l);
  188. }
  189.  
  190. void print(node *t) {
  191.     if (t == nullptr) return;
  192.     print(t->l);
  193.     cerr << t->val << ' ';
  194.     print(t->r);
  195. }
  196.  
  197. void write(node *t) {
  198.     cerr << "-----------------\n";
  199.     print(t);
  200.     cerr << "\n-----------------\n";
  201. }
  202.  
  203. void debug_node(node *v, string pref = "") {
  204.     if (v != nullptr) {
  205.         v->push();
  206.         debug_node(v->r, pref + " ");
  207.         cerr << pref << "-" << " " << v->val << '\n';
  208.         debug_node(v->l, pref + " ");
  209.     } else {
  210.         cerr << pref << "-" << " " << "nullptr " << '\n';
  211.     }
  212. }
  213.  
  214. int query(node* v, node* u) {
  215.     if (!path(v, u)) return 0;
  216.  
  217.     evert(v);
  218.     expose(u);
  219.  
  220.     return u->res;
  221. }
  222.  
  223. void update(node* v, node* u, int value) {
  224.     if (!path(v, u))
  225.         return;
  226.  
  227.     evert(v);
  228.     expose(u);
  229.  
  230.     u->d += value;
  231. }
  232.  
  233. void solveTestCase() {
  234.     int n;
  235.     cin >> n;
  236.  
  237.     vector<node*> tree(n);
  238.  
  239.     rep(i, 0, n) {
  240.         int w;
  241.         cin >> w;
  242.         tree[i] = new node(i, w);
  243.     }
  244.  
  245.     rep(i, 0, n - 1) {
  246.         int v, u;
  247.         cin >> v >> u;
  248.         --v, --u;
  249.  
  250.         link(tree[v], tree[u]);
  251.     }
  252.  
  253.     int m;
  254.     cin >> m;
  255.  
  256.     rep(i, 0, m) {
  257.         char t = '?';
  258.  
  259.         cin >> t;
  260.  
  261.         if (t == '?') {
  262.             int v, u;
  263.             cin >> v >> u;
  264.             --v, --u;
  265.  
  266.             cout << query(tree[v], tree[u]) << '\n';
  267.         } else {
  268.             int v, x;
  269.             cin >> v >> x;
  270.             --v;
  271.  
  272.             update(tree[v], tree[v], x - query(tree[v], tree[v]));
  273.         }
  274.     }
  275. }
  276.  
  277. signed main() {
  278.     ioBoost;
  279.     int tt = 1;
  280. //    cin >> tt;
  281.     while (tt--)
  282.         solveTestCase();
  283. }
RAW Paste Data