Advertisement
fedor-resh

Untitled

May 3rd, 2024
802
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <functional>
  5.  
  6. using ll = long long;
  7. using namespace std;
  8. ll inf = 1e10;
  9.  
  10. #define p(v) for (auto x : v) cout << x << " "; cout << endl;
  11.  
  12. struct SegTree {
  13.     struct Node {
  14.         Node(ll val = 0) : val(val) {};
  15.         ll val = 0;
  16.         ll min = inf;
  17.         ll push = 0;
  18.     };
  19.  
  20.     vector<Node> tree;
  21.     ll size;
  22.  
  23.     Node combine(Node a, Node b) {
  24.         return Node(a.val + b.val);
  25.     }
  26.  
  27.     SegTree(ll n) {
  28.         size = n;
  29.         tree.resize(size * 4);
  30.     }
  31.  
  32.     SegTree(vector<ll> &arr) {
  33.         size = arr.size();
  34.         tree.resize(size * 4);
  35.         build(0, 0, size, arr);
  36.     }
  37.  
  38.     void build(ll v, ll l, ll r, vector<ll> &arr) {
  39.         if (l + 1 == r) {
  40.             tree[v] = Node(arr[l]);
  41.             return;
  42.         }
  43.         ll m = (l + r) / 2;
  44.         build(v * 2 + 1, l, m, arr);
  45.         build(v * 2 + 2, m, r, arr);
  46.         tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
  47.     }
  48.  
  49.     void print() {
  50.         for (ll i = 0; i < size * 4; i++) {
  51.             cout << tree[i].val << " ";
  52.         }
  53.         cout << endl;
  54.     }
  55.  
  56.     void update(ll v, ll l, ll r, ll pos, ll val) {
  57.         if (l + 1 == r) {
  58.             tree[v] = val;
  59.             return;
  60.         }
  61.         ll m = (l + r) / 2;
  62.         if (pos < m) {
  63.             update(v * 2 + 1, l, m, pos, val);
  64.         } else {
  65.             update(v * 2 + 2, m, r, pos, val);
  66.         }
  67.         tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
  68.     }
  69.  
  70.     void update(ll pos, ll val) {
  71.         update(0, 0, size, pos, val);
  72.     }
  73.  
  74.     Node get(ll v, ll cl, ll cr, ll l, ll r) {
  75.         if (r <= cl || cr <= l) {
  76.             return 0;
  77.         }
  78.         if (l <= cl && cr <= r) {
  79.             return tree[v];
  80.         }
  81.         ll mid = (cl + cr) / 2;
  82.         Node lval = get(v * 2 + 1, cl, mid, l, r);
  83.         Node rval = get(v * 2 + 2, mid, cr, l, r);
  84.         return combine(lval, rval);
  85.     };
  86.  
  87.     ll get(ll l, ll r) {
  88.         return get(0, 0, size, l, r).val;
  89.     };
  90. };
  91.  
  92.  
  93. struct LCA_graph {
  94.     ll k, n;
  95.     vector<vector<ll>> up;
  96.     vector<ll> h;
  97.  
  98.     LCA_graph(vector<vector<ll>> &adj) {
  99.         n = adj.size();
  100.         k = 20;
  101.         up.resize(n, vector<ll>(k, -1));
  102.         h.resize(n, 0);
  103.         build(adj, 0);
  104.     }
  105.  
  106.     void build(vector<vector<ll>> &adj, ll v, ll p = -1) {
  107.         if (p == -1) p = v;
  108.         up[v][0] = p;
  109.         for (ll i = 1; i < k; ++i) {
  110.             if (up[v][i - 1] != -1)
  111.                 up[v][i] = up[up[v][i - 1]][i - 1];
  112.         }
  113.         for (ll u: adj[v]) {
  114.             if (u != p) {
  115.                 h[u] = h[v] + 1;
  116.                 build(adj, u, v);
  117.             }
  118.         }
  119.     }
  120.  
  121.     ll lca(ll a, ll b) {
  122.         if (h[a] < h[b]) swap(a, b);
  123.         a = raise(a, h[a] - h[b]);
  124.         if (a == b) return a;
  125.         for (ll sz = k - 1; sz >= 0; --sz) {
  126.             if (up[a][sz] != up[b][sz]) {
  127.                 a = up[a][sz];
  128.                 b = up[b][sz];
  129.             }
  130.         }
  131.         return up[a][0];
  132.     }
  133.  
  134. private:
  135.     ll raise(ll a, ll height) {
  136.         for (ll sz = k - 1; sz >= 0; --sz) {
  137.             if ((height & (1 << sz))) {
  138.                 a = up[a][sz];
  139.             }
  140.         }
  141.         return a;
  142.     }
  143. };
  144.  
  145. vector<ll> get_children_count(vector<vector<ll>> &adj, ll v = 0) {
  146.     vector<ll> children_count(adj.size(), 0);
  147.     function<void(ll, ll)> dfs = [&](ll v, ll p) {
  148.         children_count[v] = 1;
  149.         for (ll u: adj[v]) {
  150.             if (u == p) continue;
  151.             dfs(u, v);
  152.             children_count[v] += children_count[u];
  153.         }
  154.     };
  155.     dfs(v, -1);
  156.     return children_count;
  157. }
  158.  
  159. class HeavyLightDecomposition {
  160. public:
  161.     vector<vector<ll>> &adj;
  162.     SegTree tree;
  163.     LCA_graph lca;
  164.     ll tin = 0;
  165.     struct Node {
  166.         ll head;
  167.         ll tin;
  168.         ll pos_in_seg_tree;
  169.     };
  170.     vector<Node> nodes;
  171.     vector<ll> &weights;
  172.  
  173.     HeavyLightDecomposition(vector<vector<ll>> &adj, vector<ll> &weights) : adj(adj), lca(LCA_graph(adj)), tree(SegTree(adj.size())), nodes(vector<Node>(adj.size())), weights(weights) {
  174.         build_hld();
  175.     }
  176.  
  177.     void build_hld() {
  178.         ll n = adj.size();
  179.         vector<ll> children_count = get_children_count(adj);
  180.         nodes.resize(n);
  181.         function<void(ll, ll)> dfs = [&](ll v, ll p) {
  182.             nodes[v].tin = tin++;
  183.             ll max_child = -1;
  184.             ll max_size = 0;
  185.             for (ll u: adj[v]) {
  186.                 if (u == p) continue;
  187.                 if (children_count[u] > max_size) {
  188.                     max_size = children_count[u];
  189.                     max_child = u;
  190.                 }
  191.             }
  192.             if (max_child != -1) {
  193.                 nodes[max_child].head = nodes[v].head;
  194.                 dfs(max_child, v);
  195.             }
  196.             for (ll u: adj[v]) {
  197.                 if (u == p || u == max_child) continue;
  198.                 nodes[u].head = u;
  199.                 dfs(u, v);
  200.             }
  201.         };
  202.         nodes[0].head = 0;
  203.         dfs(0, -1);
  204.         vector<ll> arr(n);
  205.         for (ll i = 0; i < n; ++i) {
  206.             arr[nodes[i].tin] = weights[i];
  207.             nodes[i].pos_in_seg_tree = nodes[i].tin;
  208.         }
  209.         tree = SegTree(arr);
  210.     }
  211.  
  212.     ll query(ll a, ll b) {
  213.         ll res = 0;
  214.         ll lca_ab = lca.lca(a, b);
  215.         while (nodes[a].head != nodes[lca_ab].head) {
  216.             res += tree.get(nodes[nodes[a].head].tin, nodes[a].tin + 1);
  217.             a = lca.up[nodes[a].head][0];
  218.         }
  219.         while (nodes[b].head != nodes[lca_ab].head) {
  220.             res += tree.get(nodes[nodes[b].head].tin, nodes[b].tin + 1);
  221.             b = lca.up[nodes[b].head][0];
  222.         }
  223.         res += tree.get(min(nodes[a].tin, nodes[b].tin), max(nodes[a].tin, nodes[b].tin) + 1);
  224.         return res;
  225.     }
  226.  
  227.     void set(ll a, ll val) {
  228.         tree.update(nodes[a].pos_in_seg_tree, val);
  229.     }
  230. };
  231.  
  232. signed main() {
  233.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  234.     ll n;
  235.     cin >> n;
  236.     vector<vector<ll>> adj(n);
  237.     vector<ll> weights(n);
  238.     for (ll i = 1; i < n; ++i) {
  239.         ll p;
  240.         cin >> p;
  241.         adj[p].push_back(i);
  242.         adj[i].push_back(p);
  243.     }
  244.  
  245.     for (ll i = 0; i < n; ++i) {
  246.         cin >> weights[i];
  247.     }
  248.  
  249.  
  250.     HeavyLightDecomposition hld(adj, weights);
  251.     ll q;
  252.     cin >> q;
  253.     while (q--) {
  254.         string com;
  255.         ll a, b;
  256.         cin >> com >> a >> b;
  257.         if (com[0] == 'A') {
  258.             hld.set(a, b);
  259.         }else{
  260.             cout << hld.query(a, b) << "\n";
  261.         }
  262.     }
  263.  
  264.     return 0;
  265. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement