#include using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair P; typedef vector vec; using Graph = vector>; const long long INF = 1LL<<60; const long long MOD = 1000000007; #ifndef ATCODER_INTERNAL_BITOP_HPP #define ATCODER_INTERNAL_BITOP_HPP 1 #ifdef _MSC_VER #include #endif #if __cplusplus >= 202002L #include #endif namespace atcoder { namespace internal { #if __cplusplus >= 202002L using std::bit_ceil; #else // @return same with std::bit::bit_ceil unsigned int bit_ceil(unsigned int n) { unsigned int x = 1; while (x < (unsigned int)(n)) x *= 2; return x; } #endif // @param n `1 <= n` // @return same with std::bit::countr_zero int countr_zero(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } // @param n `1 <= n` // @return same with std::bit::countr_zero constexpr int countr_zero_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } } // namespace internal } // namespace atcoder #endif // ATCODER_INTERNAL_BITOP_HPP #ifndef ATCODER_LAZYSEGTREE_HPP #define ATCODER_LAZYSEGTREE_HPP 1 #include #include #include #include namespace atcoder { #if __cplusplus >= 201703L template struct lazy_segtree { static_assert(std::is_convertible_v>, "op must work as S(S, S)"); static_assert(std::is_convertible_v>, "e must work as S()"); static_assert( std::is_convertible_v>, "mapping must work as F(F, S)"); static_assert( std::is_convertible_v>, "compostiion must work as F(F, F)"); static_assert(std::is_convertible_v>, "id must work as F()"); #else template struct lazy_segtree { #endif public: lazy_segtree() : lazy_segtree(0) {} explicit lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} explicit lazy_segtree(const std::vector& v) : _n(int(v.size())) { size = (int)internal::bit_ceil((unsigned int)(_n)); log = internal::countr_zero((unsigned int)size); d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder #endif // ATCODER_LAZYSEGTREE_HPP using namespace atcoder; // auto mod int // https://youtu.be/L8grWxBlIZ4?t=9858 // https://youtu.be/ERZuLAxZffQ?t=4807 : optimize // https://youtu.be/8uowVvQ_-Mo?t=1329 : division const int mod = 1000000007; struct mint { ll x; // typedef long long ll; mint(ll x=0):x((x%mod+mod)%mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;} mint operator+(const mint a) const { return mint(*this) += a;} mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) const { return mint(*this) /= a;} }; istream& operator>>(istream& is, mint& a) { return is >> a.x;} ostream& operator<<(ostream& os, const mint& a) { return os << a.x;} struct S{ mint value; mint size; }; using F = ll; const F ID = 0; S op(S a, S b){ return {a.value+b.value, a.size+b.size}; } S e(){ return {0, 0}; } S mapping(F f, S x){ x.value += x.size*f; return x; } F composition(F f, F g){ return f+g; } F id(){ return ID; } /* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体 query(u,v): u と v の LCA を求める。計算量 O(logn) 前処理: O(nlogn)時間, O(nlogn)空間 */ struct LCA { vector> parent; // parent[k][u]:= u の 2^k 先の親 vector dist; // root からの距離 LCA(const Graph& G, int root) { init(G, root); } // 初期化 void init(const Graph& G, int root) { int V = G.size(); int K = 1; while ((1 << K) < V) K++; //KはK>=log2(V)を満たす最小の整数 parent.assign(K, vector(V, -1)); dist.assign(V, -1); dfs(G, root, -1, 0); for (int k = 0; k + 1 < K; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } // 根からの距離と1つ先の頂点を求める void dfs(const Graph& G, int v, int p, int d) { parent[0][v] = p; dist[v] = d; for (auto e : G[v]) { if (e!= p) dfs(G, e, v, d + 1); } } int query(int u, int v) { if (dist[u] < dist[v]) swap(u, v); // u の方が深いとする int K = parent.size(); // LCA までの距離を同じにする for (int k = 0; k < K; k++) { if ((dist[u] - dist[v]) >> k & 1) { u = parent[k][u]; } } // 二分探索で LCA を求める if (u == v) return u; for (int k = K - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); ll n;cin>>n; vec a(n); vec b(n); rep(i,n)cin>>a[i]; rep(i,n)cin>>b[i]; Graph g(n); rep(i,n-1){ ll a,b;cin>>a>>b; a--;b--; g[a].push_back(b); g[b].push_back(a); } vec sub(n); function dfs=[&](ll x,ll p){ ll res=1; for(ll &nx:g[x]){ if(nx==p)continue; res+=dfs(nx,x); if(sub[nx]>sub[g[x][0]])swap(g[x][0],nx); } return sub[x]=res; }; dfs(0,-1); vec par(n); vec ord(n); vec head(n); ll idx=0; function efs=[&](ll x,ll p){ ord[x]=idx++; for(ll nx:g[x]){ if(nx==p)continue; par[nx]=x; if(nx==g[x][0]){ head[nx]=head[x]; } else head[nx]=nx; efs(nx,x); } }; efs(0,-1); ll q;cin>>q; vector v(n); LCA lca(g,0); rep(i,n){ v[ord[i]]={a[i],b[i]}; } lazy_segtree seg(v); rep(qi,q){ ll ty;cin>>ty; ll x,y,z; if(ty==0){ cin>>x>>y>>z; x--;y--; ll lc=lca.query(x,y); while(ord[x]>=ord[lc]){ ll R=ord[x]; ll L=ord[head[x]]; chmax(L,ord[lc]); seg.apply(L,R+1,z); if(L==ord[lc])break; x=par[head[x]]; } while(ord[y]>ord[lc]){ ll R=ord[y]; ll L=ord[head[y]]; chmax(L,ord[lc]+1); seg.apply(L,R+1,z); if(L==ord[lc]+1)break; y=par[head[y]]; } } else{ cin>>x>>y; x--;y--; ll lc=lca.query(x,y); mint ans=0; while(ord[x]>=ord[lc]){ ll R=ord[x]; ll L=ord[head[x]]; chmax(L,ord[lc]); ans+=seg.prod(L,R+1).value; if(L==ord[lc])break; x=par[head[x]]; } while(ord[y]>ord[lc]){ ll R=ord[y]; ll L=ord[head[y]]; chmax(L,ord[lc]+1); ans+=seg.prod(L,R+1).value; if(L==ord[lc]+1)break; y=par[head[y]]; } cout<