#include #include using namespace std; using namespace atcoder; //using mint = modint998244353; //const int mod = 998244353; //using mint = modint1000000007; //const int mod = 1000000007; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } #include using S = long long; S op(S a, S b) { return a + b; } S e() { return 0; } struct HeavyLightDecomposition { HeavyLightDecomposition(std::vector> &_g, std::vector&_val) :g(_g), val(_val) { n = g.size(); sz.resize(n); par.resize(n); in.resize(n); out.resize(n); rev.resize(n); head.resize(n); deep.resize(n); } int n; std::vector>g; std::vectorsz, par, in, out, rev, head, deep; std::vectorval; segtreeseg; void build() { dfs_sz(0); int time = 0; dfs_hld(0, time); initSegmentTree(); } void dfs_sz(int v, int d = 0, int p = -1) { deep[v] = d; par[v] = p; sz[v] = 1; if (g[v].size() && (p == g[v][0]))std::swap(g[v][0], g[v].back()); for (auto &e : g[v]) { if (p == e)continue; dfs_sz(e, d + 1, v); sz[v] += sz[e]; if (sz[g[v][0]] < sz[e])std::swap(g[v][0], e); } } void dfs_hld(int v, int &time, int p = -1) { in[v] = time; time++; rev[in[v]] = v; for (auto &e : g[v]) { if (p == e)continue; if (e == g[v][0])head[e] = head[v]; else head[e] = e; dfs_hld(e, time, v); } out[v] = time; } void initSegmentTree() { std::vector_val(n); for (int i = 0; i < n; ++i)_val[i] = val[rev[i]]; seg = segtree(_val); } S query(int u, int v) { S ret = e(); for (;; v = par[head[v]]) { if (in[u] > in[v])std::swap(u, v); if (head[u] == head[v])break; auto get = seg.prod(in[head[v]], in[v] + 1); ret = op(ret, get); } auto get = seg.prod(in[u], in[v] + 1); ret = op(ret, get); return ret; } int la(int v, int k) { while (1) { int u = head[v]; if (in[v] - k >= in[u])return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for (;; v = par[head[v]]) { if (in[u] > in[v])std::swap(u, v); if (head[u] == head[v])return u; } } int dist(int u, int v) { return deep[u] + deep[v] - 2 * deep[lca(u, v)]; } // point update void update_point(int u, S x) { seg.set(in[u], x); } void debug() { for (int i = 0; i < n; ++i) std::cout << seg.prod(i, i + 1) << " "; std::cout << std::endl; } }; #include #include class Tree { public: Tree(int n, int root) : n(n), root(root) { edge.resize(n); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n); depth.resize(n); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfs(root, -1, 0); for (int k = 0; k + 1 < MAXLOGV; k++) { for (int v = 0; v < n; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uのn個親を求める int pare(int v, int n) { if (depth[v] < n)return -1; n = std::min(n, depth[v]); int idx = MAXLOGV; while (n) { for (int i = idx - 1; i >= 0; --i) { if (n < (1 << i))continue; if (-1 == parent[i][v])continue; n -= (1 << i); v = parent[i][v]; idx = i; break; } } return v; } // uからvに向かってd進んだ頂点を返す int JumpOnTree(int u, int v, int d) { if (0 == d)return u; int distuv = dist(u, v); if (distuv < d)return -1; int l = lca(u, v); if (l == u)return pare(v, distuv - d); if (l == v)return pare(u, d); int distlu = dist(l, u); if (distlu >= d)return pare(u, d); return pare(v, distuv - d); } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u] - depth[p]) + (depth[v] - depth[p]); } //頂点wが頂点u,vのパス上に存在するか bool on_path(int u, int v, int w) { return (dist(u, w) + dist(v, w) == dist(u, v)); } int dfs(int v, int p, int d) { int ret = 1; parent[0][v] = p; depth[v] = d; for (int next : edge[v]) { if (next == p) continue; auto get = dfs(next, v, d + 1); ret += get; } return ret; } static const int MAXLOGV = 25; // グラフの隣接リスト表現 std::vector>edge; // 頂点の数 int n; // 根ノードの番号 int root; // 親ノード std::vector parent[MAXLOGV]; // 根からの深さ std::vector depth; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vectora(n + 1); rep(i, n)cin >> a[i + 1]; Tree tree(n + 1, 0); vector>g(n + 1); g[0].push_back(1); g[1].push_back(0); tree.unite(0, 1); rep(i, n - 1) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); tree.unite(a, b); } tree.init(); vectorsa(n + 1); rep2(i, 1, n + 1) { int p = tree.pare(i, 1); sa[p] += a[i]; } HeavyLightDecomposition hld(g, sa); hld.build(); while (q--) { int t; cin >> t; if (0 == t) { int v, x; cin >> v >> x; a[v] += x; int p = tree.pare(v, 1); sa[p] += x; hld.update_point(p, sa[p]); } else { int u, v; cin >> u >> v; int l = tree.lca(u, v); int p = tree.pare(l, 1); if (u == l || v == l) { long long ans = a[p] + sa[p] + hld.query(u, v); cout << ans << endl; } else { long long ans = 0; ans += hld.query(u, l); ans += hld.query(v, l); ans += a[p] + a[l] - sa[l]; cout << ans << endl; } } } return 0; }