Advertisement
trafik

Untitled

Aug 16th, 2022
533
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <string>
  5. #include <map>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <set>
  9. #include <chrono>
  10. #include <random>
  11. #include <iomanip>
  12. #include <fstream>
  13. #define ll long long
  14. #define len(v) (int)v.size()
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(), v.rend()
  17. #define pii pair<int, int>
  18. #define vi vector<int>
  19. #define vii vector<vector<int>>
  20. #define ull unsigned long long
  21. //#define int long long
  22. const int maxn = 1e5 + 10;
  23. const int C = 20;
  24. const int logn = 20;
  25. const int inf = 1e9;
  26. const int mod = 1e9 + 7;
  27. const int M = 1e9;
  28. const ull M2 = 998244353;
  29. using namespace std;
  30.  
  31. int n, m, l = 1, rootval;
  32. vector<vector<int>> g, up;
  33. int timer = 0;
  34. vector<ll> a, tin, tout;
  35. vector<ll> pref;
  36.  
  37. bool ancestor(int a, int b) {
  38.     return (tin[a] <= tin[b]) && (tout[a] >= tout[b]);
  39. }
  40.  
  41. int lca(int a, int b) {
  42.     if (ancestor(a, b)) return a;
  43.     if (ancestor(b, a)) return b;
  44.     for (int i = l; i >= 0; --i) {
  45.         if (!ancestor(up[a][i], b))
  46.             a = up[a][i];
  47.     }
  48.     return up[a][0];
  49. }
  50.  
  51. void dfs(int v, int p = 1) {
  52.     tin[v] = timer++;
  53.     up[v][0] = p;
  54.     for (int i = 1; i <= l; ++i)
  55.         up[v][i] = up[up[v][i - 1]][i - 1];
  56.     for (auto u : g[v]) {
  57.         if (u != p)
  58.             dfs(u, v);
  59.     }
  60.     tout[v] = timer;
  61. }
  62.  
  63. struct segtree {
  64.     vector<ll> t;
  65.     vector<ll> a;
  66.  
  67.     void init(vector<ll>& _a) {
  68.         a = _a;
  69.         t.resize(len(a) * 4 + 10);
  70.     }
  71.     void build(int v, int l, int r) {
  72.         if (l + 1 == r) {
  73.             t[v] = a[l];
  74.             return;
  75.         }
  76.         int m = (l + r) / 2;
  77.         build(2 * v + 1, l, m);
  78.         build(2 * v + 2, m, r);
  79.     }
  80.     void upd(int v, int l, int r, int ql, int qr, int x) {
  81.         if (ql >= qr) return;
  82.         if (l >= r) return;
  83.         if (l == ql && r == qr) {
  84.             t[v] += x;
  85.             return;
  86.         }
  87.         int m = (l + r) / 2;
  88.         upd(2 * v + 1, l, m, ql, min(qr, m), x);
  89.         upd(2 * v + 2, m, r, max(ql, m), qr, x);
  90.     }
  91.     ll get(int v, int l, int r, int pos) {
  92.         if (l + 1 == r)
  93.             return t[v];
  94.         int m = (l + r) / 2;
  95.         if (pos < m)
  96.             return t[v] + get(2 * v + 1, l, m, pos);
  97.         else
  98.             return t[v] + get(2 * v + 2, m, r, pos);
  99.     }
  100. };
  101.  
  102. void dfspref(int v, ll curs) {
  103.     pref[tin[v]] = curs + a[v];
  104.     curs += a[v];
  105.     for (auto u : g[v]) {
  106.         if (u != up[v][0])
  107.             dfspref(u, curs);
  108.     }
  109. }
  110.  
  111. ll getval(int v, segtree& t) {
  112.     if (v == 1)
  113.         return rootval;
  114.     return (t.get(0, 0, n, tin[v]) - t.get(0, 0, n, tin[up[v][0]]));
  115. }
  116.  
  117. void solve() {
  118.     cin >> n;
  119.     g.resize(n + 1);
  120.     up.resize(n + 1);
  121.     for (auto& e : up)
  122.         e.resize(logn);
  123.     tin.resize(n + 1);
  124.     tout.resize(n + 1);
  125.     a.resize(n + 1);
  126.     pref.resize(n);
  127.  
  128.     for (int i = 1; i <= n; ++i)
  129.         cin >> a[i];
  130.     for (int i = 1; i < n; ++i) {
  131.         int u, v; cin >> u >> v;
  132.         g[u].push_back(v);
  133.         g[v].push_back(u);
  134.     }
  135.     dfs(1);
  136.     dfspref(1, 0ll);
  137.     rootval = a[1];
  138.  
  139.     segtree t;
  140.     t.init(pref);
  141.     t.build(0, 0, n);
  142.  
  143.     cin >> m;
  144.     while (m--) {
  145.         char tp; cin >> tp;
  146.         if (tp == '?') {
  147.             int u, v; cin >> u >> v;
  148.             int lcauv = lca(u, v);
  149.             ll lcas = t.get(0, 0, n, tin[lcauv]);
  150.  
  151.             ll lcaval = getval(lcauv, t);
  152.  
  153.             cout << (t.get(0, 0, n, tin[u]) + t.get(0, 0, n, tin[v]) - lcas - lcas + lcaval) << "\n";
  154.         }
  155.         else {
  156.             int v, x; cin >> v >> x;
  157.             t.upd(0, 0, n, tin[v], tout[v], (x - getval(v, t)));
  158.             if (v == 1)
  159.                 rootval = x;
  160.         }
  161.     }
  162.  
  163. }
  164.  
  165. signed main() {
  166.     ios::sync_with_stdio(0);
  167.     cin.tie(0);
  168.     cout.tie(0);
  169.  
  170.     solve();
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement