#include using namespace std; struct CentroidPathDecomposition { struct Centroid { int ParIndex, ParDepth, Deep; vector< int > node; Centroid(int idx, int dep, int deep) : ParIndex(idx), ParDepth(dep), Deep(deep) {} inline size_t size() { return (node.size()); } inline int &operator[](int k) { return (node[k]); } inline pair< int, int > Up() { return (make_pair(ParIndex, ParDepth)); } }; vector< vector< int > > graph; vector< int > SubTreeSize, NextPath; vector< int > TreeIndex, TreeDepth; vector< Centroid > Centroids; void BuildSubTreeSize() { stack< pair< int, int > > s; s.emplace(0, -1); while(!s.empty()) { auto p = s.top(); s.pop(); if(~SubTreeSize[p.first]) { NextPath[p.first] = -1; for(auto &to : graph[p.first]) { if(p.second == to) continue; SubTreeSize[p.first] += SubTreeSize[to]; if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) { NextPath[p.first] = to; } } } else { s.push(p); SubTreeSize[p.first] = 1; for(auto &to : graph[p.first]) { if(p.second != to) s.emplace(to, p.first); } } } } void BuildPath() { stack< pair< int, int > > s; Centroids.emplace_back(-1, -1, 0); s.emplace(0, -1); TreeIndex[0] = 0; while(!s.empty()) { auto p = s.top(); s.pop(); TreeDepth[p.first] = (int) Centroids[TreeIndex[p.first]].size(); for(auto &to : graph[p.first]) { if(p.second == to) continue; if(to == NextPath[p.first]) { // Centroid-Path TreeIndex[to] = TreeIndex[p.first]; } else { // Not Centroid-Path TreeIndex[to] = (int) Centroids.size(); Centroids.emplace_back(TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1); } s.emplace(to, p.first); } Centroids[TreeIndex[p.first]].node.emplace_back(p.first); } } void AddEdge(int x, int y) { graph[x].push_back(y); graph[y].push_back(x); } virtual void Build() { BuildSubTreeSize(); BuildPath(); } inline size_t size() { return (Centroids.size()); } inline pair< int, int > Information(int idx) { return (make_pair(TreeIndex[idx], TreeDepth[idx])); } inline Centroid &operator[](int k) { return (Centroids[k]); } inline int LCA(int a, int b) { int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB; tie(TreeIdxA, TreeDepthA) = Information(a); tie(TreeIdxB, TreeDepthB) = Information(b); while(TreeIdxA != TreeIdxB) { if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) { tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up(); } else { tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up(); } } if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB); return (Centroids[TreeIdxA][TreeDepthA]); } inline virtual void query(int a, int b, const function< void(int, int, int) > &f) { int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB; tie(TreeIdxA, TreeDepthA) = Information(a); tie(TreeIdxB, TreeDepthB) = Information(b); while(TreeIdxA != TreeIdxB) { if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) { f(TreeIdxA, 0, TreeDepthA + 1); tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up(); } else { f(TreeIdxB, 0, TreeDepthB + 1); tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up(); } } if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB); f(TreeIdxA, TreeDepthA, TreeDepthB + 1); } CentroidPathDecomposition(int SZ) { graph.resize(SZ); SubTreeSize.assign(SZ, -1); NextPath.resize(SZ); TreeIndex.resize(SZ); TreeDepth.resize(SZ); } }; struct TreeArray : CentroidPathDecomposition { TreeArray(int sz) : CentroidPathDecomposition(sz) {} vector< int > index; void Build() { CentroidPathDecomposition::Build(); int ptr = 0; for(auto ¢roid : Centroids) { index.emplace_back(ptr); ptr += centroid.size(); } } inline int get(int a) { auto p = Information(a); return (index[p.first] + p.second); } inline void query(int a, int b, const function< void(int, int) > &f) { int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB; tie(TreeIdxA, TreeDepthA) = Information(a); tie(TreeIdxB, TreeDepthB) = Information(b); while(TreeIdxA != TreeIdxB) { if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) { f(index[TreeIdxA], index[TreeIdxA] + TreeDepthA + 1); tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up(); } else { f(index[TreeIdxB], index[TreeIdxB] + TreeDepthB + 1); tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up(); } } if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB); f(index[TreeIdxA] + TreeDepthA, index[TreeIdxA] + TreeDepthB + 1); } }; using int64 = long long; const int mod = 1e9 + 7; 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; } } inline void Set(int k, int x) { seg[k + sz - 1].sum += x; } inline void Build() { for(int k = sz - 2; k >= 0; k--) { seg[k].sum = (seg[2 * k + 1].sum + seg[2 * k + 2].sum) % mod; } } inline int Sum(int l, int r) { return ((Csum[r] - Csum[l] + mod) % mod); } inline 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; } inline void push(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; } } inline void add(int a, int b, int k, int z, int l, int r) { push(k, l, r); if(a >= r || b <= l) return; if(a <= l && r <= b) { (seg[k].lazy += z) %= mod; push(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); } } inline void add(int a, int b, int z) { add(a, b, 0, z, 0, sz); } inline int query(int a, int b, int k, int l, int r) { push(k, l, r); if(a >= r || b <= l) return (0); if(a <= l && r <= b) return (seg[k].sum); return ((query(a, b, 2 * k + 1, l, (l + r) >> 1) + query(a, b, 2 * k + 2, (l + r) >> 1, r)) % mod); } inline int query(int a, int b) { return (query(a, b, 0, 0, sz)); } }; int main() { int N, Q, S[200000], C[200000]; 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]); } TreeArray tree(N); for(int i = 1; i < N; i++) { int a, b; scanf("%d %d", &a, &b); tree.AddEdge(--a, --b); } tree.Build(); scanf("%d", &Q); vector< int > change(N); for(int i = 0; i < N; i++) { change[tree.get(i)] = C[i]; } SegmentTree seg(N, change); for(int i = 0; i < N; i++) { seg.Set(tree.get(i), S[i]); } seg.Build(); while(Q--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); --b, --c; if(a == 0) { int d; scanf("%d", &d); tree.query(b, c, [&](int l, int r) { seg.add(l, r, d); }); } else { int ret = 0; tree.query(b, c, [&](int l, int r) { (ret += seg.query(l, r)) %= mod; }); printf("%d\n", ret); } } }