# Untitled

Aug 16th, 2022
593
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }