#include using namespace std; using ll = long long; // #undef DEBUG // #define DEBUG /// {{{ DEBUG --- /// #ifdef DEBUG template ostream &operator<<(ostream &o, const vector &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; } #ifdef USE_COUT #define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}() #else #define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}() #endif template inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o= #ifdef USE_COUT cout; #else cerr; #endif for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; } } #else template ostream &operator<<(ostream &o, const vector &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; } #define dump(...) (42) #define dump2D(...) (42) #endif template typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple const &){} template typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple const & t){ os << (n==0?"":", ") << get(t); _ot(os, t); } template ostream & operator<<(ostream &o, tuple const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; } template ostream & operator<<(ostream &o, pair const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; } /// }}}--- /// const ll mod = 1e9 + 7; const int N = 2e5; int n; /// ModInt Library {{{ /// template struct ModInt{ private: using ll = long long; ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); } ll modinv(ll a) { ll x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; } public: long long val; constexpr ModInt() : val(0) {} constexpr ModInt(long long val) : val((val % mod + mod) % mod) {} operator int() const { return val; } operator long long() const { return val; } ModInt operator+(ModInt const &rhs) const { return ModInt(val + rhs.val); } ModInt operator-(ModInt const &rhs) const { return ModInt(val - rhs.val); } ModInt operator*(ModInt const &rhs) const { return ModInt(val * rhs.val); } ModInt operator/(ModInt const &rhs) const { return ModInt(val * rhs.inv().val); } ModInt &operator+=(ModInt const &rhs) { val = ((val + rhs.val) % mod + mod) % mod; return *this; } ModInt &operator-=(ModInt const &rhs) { val = ((val - rhs.val) % mod + mod) % mod; return *this; } ModInt &operator*=(ModInt const &rhs) { val = (val * rhs.val % mod + mod) % mod; return *this; } ModInt &operator/=(ModInt const &rhs) { val = (val * rhs.inv().val % mod + mod) % mod; return *this; } ModInt operator++(int) { ModInt tmp = *this; val = val + 1; if(val >= mod) val = 0; return tmp; } ModInt operator--(int) { ModInt tmp = *this; val = val == 0 ? mod - 1 : val - 1; return tmp; } ModInt &operator++() { val = val + 1; if(val >= mod) val = 0; return *this; } ModInt &operator--() { val = val == 0 ? mod - 1 : val - 1; return *this; } bool operator==(const ModInt &rhs) { return val == rhs.val; } template ModInt operator+(T const &rhs) const { return ModInt(val + rhs % mod); } template ModInt operator-(T const &rhs) const { return ModInt(val - rhs % mod); } template ModInt operator*(T const &rhs) const { return ModInt(val * (rhs % mod)); } template ModInt operator/(T const &rhs) const { return ModInt(val * modinv(rhs, mod)); } template ModInt &operator+=(T const &rhs) { val = ((val + rhs % mod) % mod + mod) % mod; return *this; } template ModInt &operator-=(T const &rhs) { val = ((val - rhs % mod) % mod + mod) % mod; return *this; } template ModInt &operator*=(T const &rhs) { val = (val * (rhs % mod) % mod + mod) % mod; return *this; } template ModInt &operator/=(T const &rhs) { val = (val * modinv(rhs, mod) % mod + mod) % mod; return *this; } ModInt inv() const { return ModInt(modinv(val, mod)); } friend ostream &operator<<(ostream &os, ModInt const &mv) { os << mv.val; return os; } friend constexpr ModInt operator+(long long a, ModInt const &mv) { return ModInt(a % mod + mv.val); } friend constexpr ModInt operator-(long long a, ModInt const &mv) { return ModInt(a % mod - mv.val); } friend constexpr ModInt operator*(long long a, ModInt const &mv) { return ModInt(a % mod * mv.val); } friend constexpr ModInt operator/(long long a, ModInt const &mv) { return ModInt(a % mod * mv.inv().val); } }; /// }}}-- /// using Int = ModInt; /// --- Graph Template {{{ /// template struct Edge { int from, to; T cost; Edge(int to, T cost) : from(-1), to(to), cost(cost) {} Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} }; template using WeightedGraph = vector< vector< Edge > >; using UnWeightedGraph = vector< vector >; /// }}}--- /// ll s[N], c[N]; // query(hi, lo, func, inclusive?) // hld[i] : index on sequence // WARN : build after adding edges! /// --- HL-Decomposition Library {{{ /// struct HLD { int n; vector head; vector sz; vector dep; vector par; vector vid; int id = 0; UnWeightedGraph g; // tree HLD(int n): n(n), head(n), sz(n), dep(n), par(n), vid(n), g(n) {} HLD(UnWeightedGraph g, int root = 0): HLD(g.size()) { this->g = g; build(root); } int operator[](int i) { return vid[i]; } void addEdge(int a, int b) { g[a].emplace_back(b); g[b].emplace_back(a); } void build(int root = 0) { head[root] = root; dfs0(root, -1, 0); dfs1(root, -1); } int lca(int a, int b) { while(1) { if(vid[a] > vid[b]) swap(a, b); if(head[a] == head[b]) return a; b = par[head[b]]; } } void query(int hi, int lo, function f, bool inclusive = true) { while(lo != -1 && dep[lo] >= dep[hi]) { int nex = max(vid[head[lo]], vid[hi]); f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1); lo = par[head[lo]]; } } private: void dfs0(int i, int p, int d) { par[i] = p; sz[i] = 1; dep[i] = d; for(int &j : g[i]) if(j != p) { dfs0(j, i, d + 1); sz[i] += sz[j]; if(sz[j] > sz[g[i][0]]) { swap(g[i][0], j); } } } void dfs1(int i, int p) { vid[i] = id++; for(int j : g[i]) if(j != p) { head[j] = j == g[i][0] ? head[i] : j; dfs1(j, i); } } }; /// }}}--- /// vector csum(N); Int getC(int l, int r) { Int res = csum[r-1]; if(l-1>=0) res -= csum[l-1]; return res; } // NOTE : query in range! /// --- LazySegmentTree Library {{{ /// // struct Monoid { // using T = _underlying_set_; // static T op(const T& a, const T& b) { return _a_op_b_; } // static constexpr T identity() { return _identity_element_; } // }; // struct M_act { // using M = _underlying_set_; // using X = _data_monoid_::T; // static X op(const M &a, const M &b) // { return _a_op_b_; } // static constexpr X identity() // { return _identity_element_; } // static X actInto(const M &m, long long n, const X &x) // { return _m_act_n_of_x_; } // }; template struct LazySegTree { private: using X = typename Monoid::T; using M = typename M_act::M; int n, h; std::vector data; std::vector lazy; // call before use data[i] void eval(int i, int sz) { if(lazy[i] == M_act::identity()) return; data[i] = M_act::actInto(lazy[i], sz, data[i]); if(i < n) { lazy[i * 2] = M_act::op(lazy[i], lazy[i * 2]); lazy[i * 2 + 1] = M_act::op(lazy[i], lazy[i * 2 + 1]); } lazy[i] = M_act::identity(); } // call before use seg[i] = data[i + n] void evalDown(int i) { i += n; for(int j = h - 1; j >= 0; j--) eval(i >> j, 1 << j); } // call after touch seg[i] = data[i + n] void propUp(int i) { i += n; int sz = 1; while(i >>= 1) eval(i * 2, sz), eval(i * 2 + 1, sz), data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]), sz <<= 1; } int logbin(int x) { int h = 0; x = x & 0xFFFF0000 ? (h += 16, x) & 0xFFFF0000 : x; x = x & 0xFF00FF00 ? (h += 8, x) & 0xFF00FF00 : x; x = x & 0xF0F0F0F0 ? (h += 4, x) & 0xF0F0F0F0 : x; x = x & 0xCCCCCCCC ? (h += 2, x) & 0xCCCCCCCC : x; x = x & 0xAAAAAAAA ? (h += 1, x) & 0xAAAAAAAA : x; return h; } public: LazySegTree(): n(0) {} LazySegTree(int n): n(n) { h = logbin(n) + 1; data.resize(2 * n, Monoid::identity()); lazy.resize(2 * n, M_act::identity()); } template ::value_type> LazySegTree(InputIter first, InputIter last) : LazySegTree(std::distance(first, last)) { copy(first, last, std::begin(data) + n); for(int i = n - 1; i > 0; i--) // fill from deep data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]); } void act(int l, int r, const M &m) { evalDown(l); evalDown(r - 1); int tl = l, tr = r; int sz = 1; for(l += n, r += n; l < r; l >>= 1, r >>= 1, sz <<= 1) { if(l & 1) eval(l, sz), lazy[l] = m, eval(l, sz), l++; if(r & 1) --r, eval(r, sz), lazy[r] = m, eval(r, sz); } propUp(tl); propUp(tr - 1); } void set(int i, const X &x) { evalDown(i); data[i + n] = x; propUp(i); } X get(int i) { evalDown(i); return data[i + n]; } X query(int l, int r) { evalDown(l); evalDown(r - 1); X tmpL = Monoid::identity(), tmpR = Monoid::identity(); int sz = 1; int pl = l, pr = r; for(l += n, r += n; l < r; l >>= 1, r >>= 1, sz <<= 1) { // if(l & 1) eval(l, sz), tmpL = Monoid::op(tmpL, data[l]), l++, pl += sz; // if(r & 1) --r, pr -= sz, eval(r, sz), tmpR = Monoid::op(data[r], tmpR); if(l & 1) eval(l, sz), tmpL = Monoid::op(tmpL, data[l] * getC(pl, pl + sz)), l++, pl += sz; if(r & 1) --r, pr -= sz, eval(r, sz), tmpR = Monoid::op(data[r] * getC(pr, pr + sz), tmpR); } return Monoid::op(tmpL, tmpR); } inline void dum(int r = -1) { #ifdef DEBUG std::ostream & o = #ifdef USE_COUT std::cout #else std::cerr #endif ; if(r < 0) r = n; o << "{"; for(int i = 0; i < std::min(r, n); i++) o << (i ? ", " : "") << get(i); o << "}" << std::endl; #endif } }; /// }}}--- /// // Monoid, M_act expamles {{{ struct RangeMin { using T = long long; static T op(const T& a, const T& b) { return std::min(a, b); } static constexpr T identity() { return std::numeric_limits::max(); } }; struct RangeMax { using T = long long; static T op(const T& a, const T& b) { return std::max(a, b); } static constexpr T identity() { return std::numeric_limits::min(); } }; struct RangeSum { using T = Int; static T op(const T& a, const T& b) { return a + b; } static constexpr T identity() { return T(); } }; // MinAdd m + x // MinSet m // SumAdd m * n + x // SumSet m * n struct RangeMinAdd { using M = long long; using X = RangeMin::T; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M & m, long long, const X & x) { return m + x; } }; struct RangeMinSet { using M = long long; using X = RangeMin::T; static M op(const M &a, const M &) { return a; } static constexpr M identity() { return std::numeric_limits::min(); } static X actInto(const M & m, long long, const X &) { return m; } }; struct RangeSumAdd { using M = Int; using X = RangeSum::T; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M & m, long long n, const X & x) { return m * n + x; } }; struct RangeSumSet { using M = long long; using X = RangeSum::T; static M op(const M &a, const M &) { return a; } static constexpr M identity() { return std::numeric_limits::min(); } static X actInto(const M & m, long long n, const X &) { return m * n; } }; // }}} LazySegTree qina(N); int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> s[i]; for(int i = 0; i < n; i++) cin >> c[i]; HLD hld(n); for(int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; hld.addEdge(a, b); } hld.build(); for(int i = 0; i < n; i++) csum[hld[i]] = c[i]; for(int i = 1; i < n; i++) csum[i] += csum[i-1]; vector ecas(n); for(int i = 0; i < n; i++) ecas[hld[i]] = s[i]; for(int i = 1; i < n; i++) ecas[i] = ecas[i] + ecas[i - 1]; int q; cin >> q; while(q--) { int c; cin >> c; if(c == 0) { // update int s, t, k; cin >> s >> t >> k; s--; t--; int lca = hld.lca(s, t); auto f = [&](int l, int r) { qina.act(l, r, k); }; hld.query(lca, s, f); hld.query(lca, t, f, 0); } else { // ask int s, t; cin >> s >> t; s--; t--; int lca = hld.lca(s, t); Int res = 0; auto f = [&](int l, int r) { res += qina.query(l, r); res += ecas[r - 1]; if(l - 1 >= 0) res -= ecas[l - 1]; }; hld.query(lca, s, f); hld.query(lca, t, f, 0); cout << res << endl; } } return 0; }