// verification-helper: PROBLEM https://judge.yosupo.jp/problem/vertex_add_path_sum
#include "src/datastructure/segment_tree.hpp"
#include "src/tree/euler_tour.hpp"
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &e : a) cin >> e;
EulerTour et(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
et.add_edge(u, v);
}
et.build();
SegmentTree st([](long long a, long long b) { return a + b; }, 0LL);
vector<long long> weight(2UL * n);
for (int v = 0; v < n; ++v) {
long long w = a[v];
auto [down, up] = et.index(v);
weight[down] = w;
weight[up] = -w;
}
st.build(weight);
while (q--) {
int c;
cin >> c;
if (c == 0) {
int p;
long long x;
cin >> p >> x;
auto update = [&](int i, int val) { st.update(i, st.at(i) + val); };
et.update_vertex(p, x, update);
} else {
int u, v;
cin >> u >> v;
long long res = 0;
auto query = [&](int l, int r) { res += st.find(l, r); };
et.query_vertex(u, v, query);
cout << res << endl;
}
}
return 0;
}
#line 1 "test/tree/euler_tour/yosupo_vertex_add_path_sum.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/vertex_add_path_sum
#line 1 "src/datastructure/segment_tree.hpp"
#include <vector>
template<class T, class F>
class SegmentTree { // 0-indexed
private:
int n_{};
std::vector<T> tree;
F f; // function<T(T, T)>
T ti;
public:
SegmentTree(F f, T ti) : f(f), ti(ti) {}
void init(int n) {
n_ = 1;
while (n_ < n) n_ *= 2;
tree.assign(2 * n_, ti);
}
void build(std::vector<T> const &v) {
int const N = v.size();
init(N);
for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
}
void update(int i, T const &x) {
i += n_;
tree[i] = x;
while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
}
T find(int l, int r) { // [l, r)
l += n_, r += n_;
T ll = ti, rr = ti;
while (l < r) {
if (l & 1) ll = f(ll, tree[l++]);
if (r & 1) rr = f(tree[--r], rr);
l >>= 1, r >>= 1;
}
return f(ll, rr);
}
T at(int i) { return tree[i + n_]; }
};
#line 1 "src/tree/euler_tour.hpp"
#line 5 "src/tree/euler_tour.hpp"
#include <algorithm>
#include <utility>
#line 9 "src/tree/euler_tour.hpp"
class EulerTour {
private:
static std::pair<int, int> min(std::pair<int, int> &a, std::pair<int, int> &b) {
return std::min(a, b);
}
std::vector<int> down, up, depth, terminal;
SegmentTree<std::pair<int, int>, decltype(&min)> st;
std::vector<std::vector<int>> G;
void dfs(int v, int p, int d) {
depth[terminal.size()] = d;
down[v] = terminal.size();
terminal.emplace_back(v);
for (int u : G[v]) {
if (u == p) continue;
dfs(u, v, d + 1);
}
depth[terminal.size()] = d - 1;
up[v] = terminal.size();
terminal.emplace_back(p);
}
public:
EulerTour(int n) : down(n), up(n), depth(n << 1), st(min, {1 << 30, -1}), G(n) {}
void add_edge(int u, int v) {
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void build(int root = 0) {
terminal.clear();
dfs(root, -1, 0);
std::vector<std::pair<int, int>> dep(terminal.size());
for (int i = 0; i < (int)terminal.size(); ++i) dep[i] = {depth[i], terminal[i]};
st.build(dep);
}
std::pair<int, int> index(int v) { return {down[v], up[v]}; };
int parent(int u, int v) { return depth[down[u]] < depth[down[v]] ? u : v; }
int child(int u, int v) { return depth[down[u]] < depth[down[v]] ? v : u; }
int lca(int u, int v) {
if (down[u] > down[v]) std::swap(u, v);
return st.find(down[u], down[v] + 1).second;
}
template<class F>
void query_vertex(int u, int v, F const &f) {
int a = lca(u, v);
f(down[a], down[u] + 1);
f(down[a] + 1, down[v] + 1);
}
template<class F>
void query_edge(int u, int v, F const &f) {
int a = lca(u, v);
f(down[a] + 1, down[u] + 1);
f(down[a] + 1, down[v] + 1);
}
template<class T, class F>
void update_vertex(int v, T x, F const &f) {
f(down[v], x);
f(up[v], -x);
}
template<class T, class F>
void update_edge(int u, int v, T x, F const &f) {
update_vertex(child(u, v), x, f);
}
};
#line 5 "test/tree/euler_tour/yosupo_vertex_add_path_sum.test.cpp"
#include <iostream>
#line 8 "test/tree/euler_tour/yosupo_vertex_add_path_sum.test.cpp"
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &e : a) cin >> e;
EulerTour et(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
et.add_edge(u, v);
}
et.build();
SegmentTree st([](long long a, long long b) { return a + b; }, 0LL);
vector<long long> weight(2UL * n);
for (int v = 0; v < n; ++v) {
long long w = a[v];
auto [down, up] = et.index(v);
weight[down] = w;
weight[up] = -w;
}
st.build(weight);
while (q--) {
int c;
cin >> c;
if (c == 0) {
int p;
long long x;
cin >> p >> x;
auto update = [&](int i, int val) { st.update(i, st.at(i) + val); };
et.update_vertex(p, x, update);
} else {
int u, v;
cin >> u >> v;
long long res = 0;
auto query = [&](int l, int r) { res += st.find(l, r); };
et.query_vertex(u, v, query);
cout << res << endl;
}
}
return 0;
}
test/tree/euler_tour/yosupo_vertex_add_path_sum.test.cpp