// Heavy Light Decomposition // // Supports the following operations on tree with weighted vertexes. // Assign/add a value to a vertex. O(log(n)) // Assign/add a value to a subtree. O(log(n)) // Assign/add a value to a path. O(log(n)^2) // Get a value of a vertex. O(log(n)) // Get sum of the values of a subtree. O(log(n)) // Get sum of the values of a path. O(log(n)^2) #include using namespace std; using vvi = vector>; constexpr long long mod = 1e9+7; template struct LazyData { T add; T assign; bool has_assign; LazyData(T v = 0, T w = 0, bool tf = false) : add(v), assign(w), has_assign(tf) {} }; template class SegTree { size_t n; int h; vector data; // data[i]: 区間i の重みづけ合計 vector weight; // weight[i]: 区間i の重み vector> lazy; // lazy[i]: 区間i の未伝搬の遅延評価データ static T combine(T L, T R) { return (L + R) % mod; } void apply(size_t i, T v, int command_type) { if (command_type == 0) { apply_assign(i, v); } else { apply_add(i, v); } } void apply_assign(size_t i, T v) { // v: value to assign data[i] = (weight[i] * v) % mod; if (i < n) { lazy[i].add = 0; lazy[i].assign = v; lazy[i].has_assign = true; } } void apply_add(size_t i, T v) { data[i] = (data[i] + (weight[i] * v) % mod) % mod; if (i < n) { if (lazy[i].has_assign) { lazy[i].assign = (lazy[i].assign + v) % mod; } else { lazy[i].add = (lazy[i].add + v) % mod; } } } void build(size_t i) { // update all the parents of node i. while (i >>= 1) if (not lazy[i].has_assign) data[i] = combine(combine(data[i * 2], data[i * 2 + 1]), (lazy[i].add * weight[i]) % mod); } void push(size_t p) { // propagates the changes from the root to node p. for (int s = h; s > 0; --s) { size_t i = p >> s; if (lazy[i].has_assign) { apply_assign(i * 2, lazy[i].assign); apply_assign(i * 2 + 1, lazy[i].assign); lazy[i].has_assign = false; } else if (lazy[i].add != 0) { apply_add(i * 2, lazy[i].add); apply_add(i * 2 + 1, lazy[i].add); lazy[i].add = 0; } } } int calc_h(size_t nn) { int hh = 1; for (; nn > 1; ++hh, nn >>= 1); return hh; } void process_command(size_t L, size_t R, T v, int command_type) { L += n; R += n; size_t L0 = L; size_t R0 = R; push(L); push(R - 1); for (; L < R; L >>= 1, R >>= 1) { if (L & 1) apply(L++, v, command_type); if (R & 1) apply(--R, v, command_type); } build(L0); build(R0 - 1); } void fill_weight(const vector &ws) { copy(begin(ws), end(ws), begin(weight) + n); for (int i = n - 1; i > 0; --i) weight[i] = combine(weight[i * 2], weight[i * 2 + 1]); } public: SegTree() : n(0), h(1), data(), weight(), lazy() {} explicit SegTree(const vector &_weight) : n(_weight.size()), h(calc_h(n)), data(2 * n, 0), weight(2 * n, 0), lazy(n) { fill_weight(_weight); } SegTree(const vector &src, const vector &_weight) : n(src.size()), h(calc_h(n)), data(2 * n, 0), weight(2 * n, 0), lazy(n) { fill_weight(_weight); for (int i = 0; i < n; ++i) data[n + i] = (src[i] * weight[n + i]) % mod; for (int i = n - 1; i > 0; --i) data[i] = combine(data[i * 2], data[i * 2 + 1]); } void init(const vector &_src, const vector &_weight) { n = _weight.size(); h = calc_h(n); data.assign(2 * n, 0); for (int i = 0; i < n; ++i) data[n + i] = _src[i]; // _src[i] * _weight[i] としていない点に注意。 for (int i = n - 1; i > 0; --i) data[i] = combine(data[i * 2], data[i * 2 + 1]); weight.assign(2 * n, 0); lazy.resize(n); fill_weight(_weight); } void modify(size_t L, size_t R, T w) { process_command(L, R, w, 0); } // assign w to range [L, R) void add(size_t L, size_t R, T v) { process_command(L, R, v, 1); } // add v to range [L, R) T query(size_t L, size_t R) { L += n; R += n; push(L); push(R - 1); T ret = 0; for (; L < R; L >>= 1, R >>= 1) { if (L & 1) ret = combine(ret, data[L++]); if (R & 1) ret = combine(data[--R], ret); } return ret; } }; class RMQidx { private: int n; // size of val vvi idx; // doubling range min index. idx[k][p]: index of min(val[p:p+2^k]) including p and not including p+2^k. vector val; void init(const vector &src) { n = src.size(); val = src; idx.emplace_back(vector(n, 0)); for (int i = 0; i != n; ++i) idx[0][i] = i; for (int k = 0, r = 1; r < n; ++k, r <<= 1) { idx.emplace_back(idx[k]); for (int p = 0; p + r < n; ++p) { auto idxL = idx[k][p]; auto idxR = idx[k][p + r]; idx[k + 1][p] = (val[idxL] > val[idxR]) ? idxR : idxL; } } } public: RMQidx() : n(0), idx(vvi()), val(vector()) {} RMQidx(const vector &src) { init(src); } int query(int L, int R) { // index of min(data[0][L..R] including both ends. [L, R] assert(L <= R); if (L == R) return L; int k = 31 - __builtin_clz(R - L); auto idxL = idx[k][L]; auto idxR = idx[k][R + 1 - (1 << k)]; return (val[idxL] > val[idxR]) ? idxR : idxL; } }; class LCA { private: int n; // number of vertexes int root; vector height; // height[v] = height of vertex v. vector i2v; // i2v[i] = v. Euler tour order of vertexes. vector v2i; // v2i[v] = i. Last position of vertex v in the Euler tour. RMQidx rmq; // Range Minimum Query object which returns the position (idx) of the minimum value in the euler tour. void dfs(int v, int h, const vvi &Es) { height[v] = h; i2v.push_back(v); for (auto u : Es[v]) { if (height[u] == -1) { dfs(u, h + 1, Es); i2v.push_back(v); } } } public: LCA(const vvi &Es, int _root = 0) : n(Es.size()), root(_root), height(n, -1), i2v(), v2i(n, -1) { dfs(root, 0, Es); assert(i2v.size() == 2 * n - 1); vector val(2 * n - 1); for (int i = 0; i != 2 * n - 1; ++i) { val[i] = height[i2v[i]]; v2i[i2v[i]] = i; } rmq = RMQidx(val); } int query(int u, int v) { // returns lowest common ancestor of vertex u and vertex v. int i = v2i[u]; int j = v2i[v]; if (i > j) swap(i, j); return i2v[rmq.query(i, j)]; } }; class HLDecompose { int n; // number of vertexes vector subtree_size; // sizes of subtrees void dfs0(int v, const vvi &Es) { subtree_size[v] = 1; for (auto u : Es[v]) { if (u == parent[v]) continue; parent[u] = v; dfs0(u, Es); subtree_size[v] += subtree_size[u]; } } int find_heavy_edge(int v, const vvi &Es) { int heavy = v; for (auto u : Es[v]) if (u != parent[v] and (subtree_size[u] > subtree_size[heavy] or heavy == v)) heavy = u; return heavy; } int dfs1(int v, int c, int r, const vvi &Es) { first[v] = c; head[v] = r; int heavy = find_heavy_edge(v, Es); if (heavy != v) c = dfs1(heavy, c + 1, r, Es); for (auto u : Es[v]) if (u != parent[v] and u != heavy) c = dfs1(u, c + 1, u, Es); last[v] = c; return c; } public: vector parent, first, last, head; HLDecompose(const vvi &Es) : n(Es.size()), subtree_size(n, 0), parent(n, n), first(n, -1), last(n, -1), head(n, -1) { dfs0(0, Es); dfs1(0, 0, 0, Es); } }; class HLDSeg { int n; LCA lca; vector parent, first, last, head; SegTree seg; void init_seg(const vector &src, const vector &ws) { assert(ws.size() == n); vector vals(n + 1, 0); for (int i = 0; i < src.size(); ++i) vals[first[i]] = src[i]; vector weights(n + 1, 0); // n + 1 個目の要素は、root の親を表すダミー頂点 for (int i = 0; i < ws.size(); ++i) weights[first[i]] = ws[i]; seg.init(vals, weights); } void modify_core(int u, int v, long long x) { // root -> u -> v -> leaf の順序とする。 for (; head[u] != head[v]; v = parent[head[v]]) seg.modify(first[head[v]], first[v] + 1, x); seg.modify(first[u], first[v] + 1, x); } void add_core(int u, int v, long long x) { // root -> u -> v -> leaf の順序とする。 for (; head[u] != head[v]; v = parent[head[v]]) seg.add(first[head[v]], first[v] + 1, x); seg.add(first[u], first[v] + 1, x); } long long query_core(int u, int v) { // root -> u -> v -> leaf の順序とする。 long long ret = 0; for (; head[u] != head[v]; v = parent[head[v]]) ret += seg.query(first[head[v]], first[v] + 1); return ret + seg.query(first[u], first[v] + 1); } public: HLDSeg(const vvi &Es, const vector & src, const vector &ws) : n(Es.size()), lca(Es), seg() { HLDecompose hld(Es); parent = hld.parent; first = hld.first; last = hld.last; head = hld.head; init_seg(src, ws); } void modify_vertex(int v, long long x) { seg.modify(first[v], first[v] + 1, x); } void add_vertex(int v, long long x) { seg.add(first[v], first[v] + 1, x); } void modify_subtree(int v, long long x) { seg.modify(first[v], last[v] + 1, x); } void add_subtree(int v, long long x) { seg.add(first[v], last[v] + 1, x); } void modify_path(int u, int v, long long x) { int w = lca.query(u, v); modify_core(w, u, x); modify_core(w, v, x); } void add_path(int u, int v, long long x) { int w = lca.query(u, v); add_core(w, u, x); add_core(w, v, x); add_vertex(w, -x); } long long query_vertex(int v) { return seg.query(first[v], first[v] + 1); } long long query_subtree(int v) { return seg.query(first[v], last[v] + 1); } long long query_path(int u, int v) { int w = lca.query(u, v); return query_core(w, u) + query_core(w, v) - query_vertex(w); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector S(N, 0); for (auto & s : S) cin >> s; vector C(N, 0); for (auto & c : C) cin >> c; vvi Es(N, vector()); for (int i = 1; i < N; ++i){ int a, b; cin >> a >> b; --a; --b; Es[a].push_back(b); Es[b].push_back(a); } HLDSeg hldseg(Es, S, C); int Q; cin >> Q; while (Q--){ int p; cin >> p; if (p == 0){ int x, y; long long z; cin >> x >> y >> z; hldseg.add_path(x - 1, y - 1, z); }else{ int x, y; cin >> x >> y; cout << hldseg.query_path(x - 1, y - 1) << '\n'; } } return 0; }