Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <functional>
- using ll = long long;
- using namespace std;
- ll inf = 1e10;
- #define p(v) for (auto x : v) cout << x << " "; cout << endl;
- struct SegTree {
- struct Node {
- Node(ll val = 0) : val(val) {};
- ll val = 0;
- ll min = inf;
- ll push = 0;
- };
- vector<Node> tree;
- ll size;
- Node combine(Node a, Node b) {
- return Node(a.val + b.val);
- }
- SegTree(ll n) {
- size = n;
- tree.resize(size * 4);
- }
- SegTree(vector<ll> &arr) {
- size = arr.size();
- tree.resize(size * 4);
- build(0, 0, size, arr);
- }
- void build(ll v, ll l, ll r, vector<ll> &arr) {
- if (l + 1 == r) {
- tree[v] = Node(arr[l]);
- return;
- }
- ll m = (l + r) / 2;
- build(v * 2 + 1, l, m, arr);
- build(v * 2 + 2, m, r, arr);
- tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
- }
- void print() {
- for (ll i = 0; i < size * 4; i++) {
- cout << tree[i].val << " ";
- }
- cout << endl;
- }
- void update(ll v, ll l, ll r, ll pos, ll val) {
- if (l + 1 == r) {
- tree[v] = val;
- return;
- }
- ll m = (l + r) / 2;
- if (pos < m) {
- update(v * 2 + 1, l, m, pos, val);
- } else {
- update(v * 2 + 2, m, r, pos, val);
- }
- tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
- }
- void update(ll pos, ll val) {
- update(0, 0, size, pos, val);
- }
- Node get(ll v, ll cl, ll cr, ll l, ll r) {
- if (r <= cl || cr <= l) {
- return 0;
- }
- if (l <= cl && cr <= r) {
- return tree[v];
- }
- ll mid = (cl + cr) / 2;
- Node lval = get(v * 2 + 1, cl, mid, l, r);
- Node rval = get(v * 2 + 2, mid, cr, l, r);
- return combine(lval, rval);
- };
- ll get(ll l, ll r) {
- return get(0, 0, size, l, r).val;
- };
- };
- struct LCA_graph {
- ll k, n;
- vector<vector<ll>> up;
- vector<ll> h;
- LCA_graph(vector<vector<ll>> &adj) {
- n = adj.size();
- k = 20;
- up.resize(n, vector<ll>(k, -1));
- h.resize(n, 0);
- build(adj, 0);
- }
- void build(vector<vector<ll>> &adj, ll v, ll p = -1) {
- if (p == -1) p = v;
- up[v][0] = p;
- for (ll i = 1; i < k; ++i) {
- if (up[v][i - 1] != -1)
- up[v][i] = up[up[v][i - 1]][i - 1];
- }
- for (ll u: adj[v]) {
- if (u != p) {
- h[u] = h[v] + 1;
- build(adj, u, v);
- }
- }
- }
- ll lca(ll a, ll b) {
- if (h[a] < h[b]) swap(a, b);
- a = raise(a, h[a] - h[b]);
- if (a == b) return a;
- for (ll sz = k - 1; sz >= 0; --sz) {
- if (up[a][sz] != up[b][sz]) {
- a = up[a][sz];
- b = up[b][sz];
- }
- }
- return up[a][0];
- }
- private:
- ll raise(ll a, ll height) {
- for (ll sz = k - 1; sz >= 0; --sz) {
- if ((height & (1 << sz))) {
- a = up[a][sz];
- }
- }
- return a;
- }
- };
- vector<ll> get_children_count(vector<vector<ll>> &adj, ll v = 0) {
- vector<ll> children_count(adj.size(), 0);
- function<void(ll, ll)> dfs = [&](ll v, ll p) {
- children_count[v] = 1;
- for (ll u: adj[v]) {
- if (u == p) continue;
- dfs(u, v);
- children_count[v] += children_count[u];
- }
- };
- dfs(v, -1);
- return children_count;
- }
- class HeavyLightDecomposition {
- public:
- vector<vector<ll>> &adj;
- SegTree tree;
- LCA_graph lca;
- ll tin = 0;
- struct Node {
- ll head;
- ll tin;
- ll pos_in_seg_tree;
- };
- vector<Node> nodes;
- vector<ll> &weights;
- 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) {
- build_hld();
- }
- void build_hld() {
- ll n = adj.size();
- vector<ll> children_count = get_children_count(adj);
- nodes.resize(n);
- function<void(ll, ll)> dfs = [&](ll v, ll p) {
- nodes[v].tin = tin++;
- ll max_child = -1;
- ll max_size = 0;
- for (ll u: adj[v]) {
- if (u == p) continue;
- if (children_count[u] > max_size) {
- max_size = children_count[u];
- max_child = u;
- }
- }
- if (max_child != -1) {
- nodes[max_child].head = nodes[v].head;
- dfs(max_child, v);
- }
- for (ll u: adj[v]) {
- if (u == p || u == max_child) continue;
- nodes[u].head = u;
- dfs(u, v);
- }
- };
- nodes[0].head = 0;
- dfs(0, -1);
- vector<ll> arr(n);
- for (ll i = 0; i < n; ++i) {
- arr[nodes[i].tin] = weights[i];
- nodes[i].pos_in_seg_tree = nodes[i].tin;
- }
- tree = SegTree(arr);
- }
- ll query(ll a, ll b) {
- ll res = 0;
- ll lca_ab = lca.lca(a, b);
- while (nodes[a].head != nodes[lca_ab].head) {
- res += tree.get(nodes[nodes[a].head].tin, nodes[a].tin + 1);
- a = lca.up[nodes[a].head][0];
- }
- while (nodes[b].head != nodes[lca_ab].head) {
- res += tree.get(nodes[nodes[b].head].tin, nodes[b].tin + 1);
- b = lca.up[nodes[b].head][0];
- }
- res += tree.get(min(nodes[a].tin, nodes[b].tin), max(nodes[a].tin, nodes[b].tin) + 1);
- return res;
- }
- void set(ll a, ll val) {
- tree.update(nodes[a].pos_in_seg_tree, val);
- }
- };
- signed main() {
- ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- ll n;
- cin >> n;
- vector<vector<ll>> adj(n);
- vector<ll> weights(n);
- for (ll i = 1; i < n; ++i) {
- ll p;
- cin >> p;
- adj[p].push_back(i);
- adj[i].push_back(p);
- }
- for (ll i = 0; i < n; ++i) {
- cin >> weights[i];
- }
- HeavyLightDecomposition hld(adj, weights);
- ll q;
- cin >> q;
- while (q--) {
- string com;
- ll a, b;
- cin >> com >> a >> b;
- if (com[0] == 'A') {
- hld.set(a, b);
- }else{
- cout << hld.query(a, b) << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement