#include using namespace std; using VI = vector; using VVI = vector; using PII = pair; using LL = long long; using VL = vector; using VVL = vector; using PLL = pair; using VS = vector; #define ALL(a) begin((a)),end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(a) int((a).size()) #define SORT(c) sort(ALL((c))) #define RSORT(c) sort(RALL((c))) #define UNIQ(c) (c).erase(unique(ALL((c))), end((c))) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define FF first #define SS second template istream& operator>>(istream& is, pair& p){ return is >> p.FF >> p.SS; } template ostream& operator<<(ostream& os, const pair& p){ return os << p.FF << " " << p.SS; } template void maxi(T& x, T y){ if(x < y) x = y; } template void mini(T& x, T y){ if(x > y) x = y; } const double EPS = 1e-10; const double PI = acos(-1.0); const LL MOD = 1000000007; struct Edge{ int to, cost; Edge(int t, int c = 0): to(t), cost(c) {} bool operator>(const Edge& rhs) const{ return cost > rhs.cost; } bool operator<(const Edge& rhs) const{ return cost < rhs.cost; } }; using Graph = vector>; void add_edge(Graph& graph, int u, int v, int cost = 0){ graph[u].push_back(Edge(v,cost)); graph[v].push_back(Edge(u,cost)); } class LazySegT{ private: int NN; struct Node{ LL dat; LL lazy; LL S; }; vector segT; public: LazySegT(int n, VL& x0, VL& s0){ NN = 1; while(NN < n) NN <<= 1; segT.resize(NN*2); for(int i=0;i=0;--i){ segT[i].dat = (segT[i*2+1].dat + segT[i*2+2].dat) % MOD; segT[i].S = (segT[i*2+1].S + segT[i*2+2].S) % MOD; segT[i].lazy = 0; } } void eval(int k, int l, int r){ if(segT[k].lazy == 0) return; (segT[k].dat += segT[k].lazy * segT[k].S % MOD) %= MOD; if(k < NN-1){ // not leaf (segT[2*k+1].lazy += segT[k].lazy) %= MOD; (segT[2*k+2].lazy += segT[k].lazy) %= MOD; } segT[k].lazy = 0; } void update(int a, int b, LL c, int k, int l, int r){ eval(k,l,r); if(r <= a || b <= l) return; if(a <= l && r <= b){ (segT[k].lazy += c) %= MOD; eval(k,l,r); } else{ update(a, b, c, k*2+1, l, (l+r)/2); update(a, b, c, k*2+2, (l+r)/2, r); segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD; } } // dat[idx] += c, a <= idx < b void update(int a, int b, LL c){ update(a, b, c, 0, 0, NN); } LL query(int a, int b, int k, int l, int r){ eval(k,l,r); if(r <= a || b <= l) return 0; if(a <= l && r <= b) return segT[k].dat; else{ LL vl = query(a, b, k*2+1, l, (l+r)/2); LL vr = query(a, b, k*2+2, (l+r)/2, r); segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD; return (vl+vr) % MOD; } } LL query(int a, int b){ return query(a, b, 0, 0, NN); } }; /** * HL分解 * * あらゆる部分木の深さがO(log n)になるように分解する。 * 部分木のうちサイズが最も大きいものへの辺をHeavy、それ以外をLightに分ける。 * Heavyな辺はたかだか一つであるのでSegment Treeなどで管理可能。 */ struct HL{ int N; VI depth; VI par; VI sz; //! 辺のコストは頂点に移す VI xs; //! 頂点が所属するHeavyのid VI heavy_id; //! 何番目の頂点か VI heavy_nth; //! heavys[id] := {idのHeavyの頂点の列} VVI heavys; //! Heavyからなる部分木としたときの親のheavy_id VI heavy_par; //! heavyの数 int H; HL(const Graph& G, int root = 0, const VI& xs_ = {}){ N = SZ(G); depth.assign(N, 0); par.assign(N, -1); sz.assign(N, 1); if(!xs_.empty()) xs = xs_; else xs.assign(N, 0); heavy_id.assign(N, -1); heavy_nth.assign(N, 0); heavys.assign(N, {}); heavy_par.assign(N, -1); function init = [&](int u, int p){ par[u] = p; for(auto& e: G[u]){ if(e.to == p) continue; depth[e.to] = depth[u] + 1; init(e.to, u); sz[u] += sz[e.to]; if(xs_.empty()) xs[e.to] = e.cost; } }; depth[root] = 0; init(root, -1); H = 1; function calcHL = [&](int u, int p){ heavy_nth[u] = SZ(heavys[heavy_id[u]]); heavys[heavy_id[u]].PB(u); int max_u = -1; for(auto& e: G[u]){ if(e.to == p) continue; if(max_u < 0 || sz[max_u] < sz[e.to]) max_u = e.to; } if(max_u < 0) return; heavy_id[max_u] = heavy_id[u]; calcHL(max_u, u); for(auto& e: G[u]){ if(e.to == p || e.to == max_u) continue; heavy_id[e.to] = H++; calcHL(e.to, u); heavy_par[heavy_id[e.to]] = heavy_id[u]; } }; heavy_id[root] = 0; calcHL(root, -1); } int LCA(int u, int v){ while(true){ if(heavy_id[u] == heavy_id[v]) return (depth[u] <= depth[v]? u: v); int ru = heavys[heavy_id[u]][0]; int rv = heavys[heavy_id[v]][0]; if(depth[ru] < depth[rv]) v = par[rv]; else u = par[ru]; } } vector segs; void initSegs(VI& cs){ REP(i,H){ int n = SZ(heavys[i]); VL x0(n), s0(n); REP(k,n){ int id = heavys[i][k]; x0[k] = xs[id]; s0[k] = cs[id]; } segs.EB(n, x0, s0); } } // Require: p is ancestor of u void add(int p, int u, LL x){ while(heavy_id[p] != heavy_id[u]){ int hid = heavy_id[u]; segs[hid].update(0, heavy_nth[u]+1, x); u = par[heavys[hid][0]]; } int hid = heavy_id[u]; segs[hid].update(heavy_nth[p], heavy_nth[u]+1, x); } // Require: p is ancestor of u LL query(int p, int u){ LL res = 0; while(heavy_id[p] != heavy_id[u]){ int hid = heavy_id[u]; (res += segs[hid].query(0, heavy_nth[u]+1)) %= MOD; u = par[heavys[hid][0]]; } int hid = heavy_id[u]; (res += segs[hid].query(heavy_nth[p], heavy_nth[u]+1)) %= MOD; return res; } }; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); int N; cin >> N; VI xs(N), cs(N); REP(i,N) cin >> xs[i]; REP(i,N) cin >> cs[i]; Graph G(N); REP(i,N-1){ int a, b; cin >> a >> b; --a; --b; add_edge(G, a, b); } auto hl = HL(G, 0, xs); hl.initSegs(cs); int Q; cin >> Q; while(Q--){ int T; int x, y, z; cin >> T >> x >> y; --x; --y; if(!T){ cin >> z; int lca = hl.LCA(x, y); hl.add(lca, x, z); hl.add(lca, y, z); hl.add(lca, lca, MOD-z); } else{ int lca = hl.LCA(x, y); cout << (hl.query(lca, x) + hl.query(lca, y) + MOD - hl.query(lca, lca))%MOD << endl; } } return 0; }