#include using namespace std; typedef long long int64; const int MOD = 1000000007; struct SegmentTree { struct node { int sum, lazy; node():sum(0), lazy(0){}; }; vector< node > seg; vector< int > Csum; int sz; SegmentTree(int n, vector< int >& C) { sz = 1; while(sz < n) sz <<= 1; seg.assign(sz * 2, node()); Csum.resize(sz + 1, 0); for(int i = 0; i < n; i++) { Csum[i + 1] = C[i]; } for(int i = 1; i < Csum.size(); i++) { (Csum[i] += Csum[i - 1]) %= MOD; } } void Set(int k, int x) { seg[k + sz - 1].sum += x; } void Build() { for(int k = sz - 2; k >= 0; k--) { seg[k].sum = (seg[2 * k + 1].sum + seg[2 * k + 2].sum) % MOD; } } int Sum(int l, int r) { return((Csum[r] - Csum[l] + MOD) % MOD); } void Update(int k, int l, int r) { (seg[k].sum = seg[2 * k + 1].sum + seg[2 * k + 2].sum) %= MOD; (seg[k].sum += (int64)Sum(l, (l + r) >> 1) * seg[2 * k + 1].lazy % MOD) %= MOD; (seg[k].sum += (int64)Sum((l + r) >> 1, r) * seg[2 * k + 2].lazy % MOD) %= MOD; } void Evaluation(int k, int l, int r) { if(seg[k].lazy == 0) return; if(k < sz - 1) { (seg[2 * k + 1].lazy += seg[k].lazy) %= MOD; (seg[2 * k + 2].lazy += seg[k].lazy) %= MOD; seg[k].lazy = 0; Update(k, l, r); } else { (seg[k].sum += (int64)Sum(l, r) * seg[k].lazy % MOD) %= MOD; seg[k].lazy = 0; } } void Add(int a, int b, int k, int z, int l, int r) { Evaluation(k, l, r); if(a >= r || b <= l) return; if(a <= l && r <= b) { (seg[k].lazy += z) %= MOD; Evaluation(k, l, r); } else { Add(a, b, 2 * k + 1, z, l, (l + r) >> 1); Add(a, b, 2 * k + 2, z, (l + r) >> 1, r); Update(k, l, r); } } void Add(int a, int b, int z) { Add(a, b, 0, z, 0, sz); } int RSQ(int a, int b, int k, int l, int r) { Evaluation(k, l, r); if(a >= r || b <= l) return(0); if(a <= l && r <= b) return(seg[k].sum); return((RSQ(a, b, 2 * k + 1, l, (l + r) >> 1) + RSQ(a, b, 2 * k + 2, (l + r) >> 1, r)) % MOD); } int RSQ(int a, int b) { return(RSQ(a, b, 0, 0, sz)); } }; struct node { int ParIdx, ParDepth, Deep, Size; } pool[200000]; typedef vector< vector< int > > Graph; Graph graph; vector< int > sz, nowIdx, nowDepth; vector< SegmentTree > segs; int ptr; vector< vector< int > > ns; inline int SizeDfs(int idx, int prev) { int ret = 0; for(int i = 0; i < graph[idx].size(); i++) { if(graph[idx][i] != prev) { ret += SizeDfs(graph[idx][i], idx); } } return(sz[idx] = ret); } inline void makeDfs(int idx, int prev, int treeIdx, int treeDepth, int Deep) { pool[treeIdx].Size++; nowIdx[idx] = treeIdx; nowDepth[idx] = treeDepth; ns[treeIdx].push_back(idx); pair< int, int > ret = make_pair(-1, -1); for(int i = 0; i < graph[idx].size(); i++) { if(graph[idx][i] != prev) { ret = max(ret, make_pair(sz[graph[idx][i]], i)); } } for(int i = 0; i < graph[idx].size(); i++) { if(graph[idx][i] != prev) { if(ret.second == i) { makeDfs(graph[idx][i], idx, treeIdx, treeDepth + 1, Deep); } else { pool[ptr++] = (node){treeIdx, treeDepth, Deep + 1, 0}; makeDfs(graph[idx][i], idx, ptr - 1, 0, Deep + 1); } } } } void CentroidPathDecomposition(const Graph& graph) { sz.resize(graph.size()); nowIdx.resize(graph.size()); nowDepth.resize(graph.size()); ns.resize(graph.size()); SizeDfs(0, -1); ptr = 0; pool[ptr++] = (node){-1, -1, 0, 0}; makeDfs(0, -1, 0, 0, 0); } void update(int A, int B, int Z) { int idx1 = nowIdx[A], dep1 = nowDepth[A]; int idx2 = nowIdx[B], dep2 = nowDepth[B]; while(idx1 != idx2) { if(pool[idx1].Deep > pool[idx2].Deep) { segs[idx1].Add(0, dep1 + 1, Z); dep1 = pool[idx1].ParDepth; idx1 = pool[idx1].ParIdx; } else { segs[idx2].Add(0, dep2 + 1, Z); dep2 = pool[idx2].ParDepth; idx2 = pool[idx2].ParIdx; } } if(dep1 > dep2) swap(dep1, dep2); segs[idx1].Add(dep1, dep2 + 1, Z); } int dist(int A, int B) { int idx1 = nowIdx[A], dep1 = nowDepth[A]; int idx2 = nowIdx[B], dep2 = nowDepth[B]; int ret = 0; while(idx1 != idx2) { if(pool[idx1].Deep > pool[idx2].Deep) { (ret += segs[idx1].RSQ(0, dep1 + 1)) %= MOD; dep1 = pool[idx1].ParDepth; idx1 = pool[idx1].ParIdx; } else { (ret += segs[idx2].RSQ(0, dep2 + 1)) %= MOD; dep2 = pool[idx2].ParDepth; idx2 = pool[idx2].ParIdx; } } if(dep1 > dep2) swap(dep1, dep2); (ret += segs[idx1].RSQ(dep1, dep2 + 1)) %= MOD; return(ret); } int N, S[200000], C[200000]; int Q; int main() { scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%d", &S[i]); } for(int i = 0; i < N; i++) { scanf("%d", &C[i]); } graph.resize(N); for(int i = 0; i < N - 1; i++) { int A, B; scanf("%d %d", &A, &B); --A, --B; graph[A].push_back(B); graph[B].push_back(A); } CentroidPathDecomposition(graph); vector< int > ll(N); for(int i = 0; i < ptr; i++) { for(int j = 0; j < ns[i].size(); j++) { ll[j] = C[ns[i][j]]; } segs.push_back(SegmentTree(ns[i].size(), ll)); for(int j = 0; j < ns[i].size(); j++) { segs[i].Set(j, S[ns[i][j]]); } segs[i].Build(); } scanf("%d", &Q); while(Q--) { int q; scanf("%d", &q); if(q == 0) { int x, y, z; scanf("%d %d %d", &x, &y, &z); update(--x, --y, z); } else { int x, y; scanf("%d %d", &x, &y); printf("%d\n", dist(--x, --y)); } } }