#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct CentroidPathDecomposition { vector colors, positions; //Vertex -> Color, Vertex -> Offset vector lengths, parents, branches; //Color -> Int, Color -> Color, Color -> Offset vector parentnodes, depths; //Vertex -> Vertex, Vertex -> Int //vectorとかを避けて1次元にしたい時に使う //sortednodesの[lefts[v], rights[v])はvのsubtreeとなっている vector sortednodes, offsets; //Index -> Vertex, Color -> Index vector lefts, rights; //Vertex -> Index struct BuildDFSState { int i, len, parent; BuildDFSState() { } BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { } }; //両方の辺があってもいいし、親から子への辺だけでもよい void build(const vector &g, int root) { int n = g.size(); colors.assign(n, -1); positions.assign(n, -1); lengths.clear(); parents.clear(); branches.clear(); parentnodes.assign(n, -1); depths.assign(n, -1); sortednodes.clear(); offsets.clear(); lefts.assign(n, -1); rights.assign(n, -1); vector subtreesizes; measure(g, root, subtreesizes); typedef BuildDFSState State; depths[root] = 0; vector s; s.push_back(State(root, 0, -1)); while(!s.empty()) { State t = s.back(); s.pop_back(); int i = t.i, len = t.len; int index = sortednodes.size(); int color = lengths.size(); if(t.parent == -3) { rights[i] = index; continue; } if(t.parent != -2) { assert(parents.size() == color); parents.push_back(t.parent); branches.push_back(len); offsets.push_back(index); len = 0; } colors[i] = color; positions[i] = len; lefts[i] = index; sortednodes.push_back(i); int maxsize = -1, maxj = -1; each(j, g[i]) if(colors[*j] == -1) { if(maxsize < subtreesizes[*j]) { maxsize = subtreesizes[*j]; maxj = *j; } parentnodes[*j] = i; depths[*j] = depths[i] + 1; } s.push_back(State(i, -1, -3)); if(maxj == -1) { lengths.push_back(len + 1); }else { each(j, g[i]) if(colors[*j] == -1 && *j != maxj) s.push_back(State(*j, len, color)); s.push_back(State(maxj, len + 1, -2)); } } } void get(int v, int &c, int &p) const { c = colors[v]; p = positions[v]; } bool go_up(int &c, int &p) const { p = branches[c]; c = parents[c]; return c != -1; } inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; } inline const int *nodesEnd(int c) const { return &sortednodes[0] + (c+1 == offsets.size() ? sortednodes.size() : offsets[c+1]); } private: void measure(const vector &g, int root, vector &out_subtreesizes) const { out_subtreesizes.assign(g.size(), -1); vector s; s.push_back(root); while(!s.empty()) { int i = s.back(); s.pop_back(); if(out_subtreesizes[i] == -2) { int s = 1; each(j, g[i]) if(out_subtreesizes[*j] != -2) s += out_subtreesizes[*j]; out_subtreesizes[i] = s; }else { s.push_back(i); each(j, g[i]) if(out_subtreesizes[*j] == -1) s.push_back(*j); out_subtreesizes[i] = -2; } } } }; template struct ModInt { static const int Mod = MOD; unsigned x; ModInt(): x(0) { } ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { signed a = x, b = MOD, u = 1, v = 0; while(b) { signed t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } if(u < 0) u += Mod; ModInt res; res.x = (unsigned)u; return res; } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; typedef ModInt<1000000007> mint; vector coefs, coefsum; typedef mint Val; struct Sum { mint sum; Sum() { } Sum(const Val &val, int pos): sum(val) { } Sum &operator+=(const Sum &that) { sum += that.sum; return *this; } Sum operator+(const Sum &that) const { return Sum(*this) += that; } }; struct Add { mint add; Add() { } Add &operator+=(const Add &that) { add += that.add; return *this; } void addToVal(Val &val, int pos) const { val += add * coefs[pos]; } void addToSum(Sum &sum, int left, int right) const { sum.sum += (coefsum[right] - coefsum[left]) * add; } }; struct SegmentTree { vector leafs; vector nodes; vector add; vector leftpos, rightpos; int n, n2; void init(int n_, const Val &v = Val()) { init(vector(n_, v)); } void init(const vector &u) { n = 1; while(n < (int)u.size()) n *= 2; n2 = (n - 1) / 2 + 1; leafs = u; leafs.resize(n, Val()); nodes.resize(n); for(int i = n-1; i >= n2; -- i) nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n); for(int i = n2-1; i > 0; -- i) nodes[i] = nodes[i*2] + nodes[i*2+1]; add.assign(n, Add()); leftpos.resize(n); rightpos.resize(n); for(int i = n-1; i >= n2; -- i) { leftpos[i] = i*2-n; rightpos[i] = (i*2+1-n) + 1; } for(int i = n2-1; i > 0; -- i) { leftpos[i] = leftpos[i*2]; rightpos[i] = rightpos[i*2+1]; } } Val get(int i) { int indices[128]; int k = getIndices(indices, i, i+1); propagateRange(indices, k); return leafs[i]; } Sum getRangeCommutative(int i, int j) { int indices[128]; int k = getIndices(indices, i, j); propagateRange(indices, k); Sum res = Sum(); for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) { if(l & 1) res += sum(l ++); if(r & 1) res += sum(-- r); } return res; } Sum getRange(int i, int j) { int indices[128]; int k = getIndices(indices, i, j); propagateRange(indices, k); Sum res = Sum(); for(; i && i + (i&-i) <= j; i += i&-i) res += sum((n+i) / (i&-i)); for(k = 0; i < j; j -= j&-j) indices[k ++] = (n+j) / (j&-j) - 1; while(-- k >= 0) res += sum(indices[k]); return res; } void set(int i, const Val &x) { int indices[128]; int k = getIndices(indices, i, i+1); propagateRange(indices, k); leafs[i] = x; mergeRange(indices, k); } void addToRange(int i, int j, const Add &x) { if(i >= j) return; int indices[128]; int k = getIndices(indices, i, j); propagateRange(indices, k); int l = i + n, r = j + n; if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); } if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); } for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) { if(l & 1) add[l ++] += x; if(r & 1) add[-- r] += x; } mergeRange(indices, k); } private: int getIndices(int indices[], int i, int j) const { int k = 0, l, r; if(i >= j) return 0; for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) { indices[k ++] = l; indices[k ++] = r; } for(; l; l >>= 1) indices[k ++] = l; return k; } void propagateRange(int indices[], int k) { for(int i = k - 1; i >= 0; -- i) propagate(indices[i]); } void mergeRange(int indices[], int k) { for(int i = 0; i < k; ++ i) merge(indices[i]); } inline void propagate(int i) { if(i >= n) return; add[i].addToSum(nodes[i], leftpos[i], rightpos[i]); if(i * 2 < n) { add[i * 2] += add[i]; add[i * 2 + 1] += add[i]; }else { add[i].addToVal(leafs[i * 2 - n], i * 2 - n); add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n); } add[i] = Add(); } inline void merge(int i) { if(i >= n) return; nodes[i] = sum(i * 2) + sum(i * 2 + 1); } inline Sum sum(int i) { propagate(i); return i < n ? nodes[i] : Sum(leafs[i - n], i - n); } }; int lowest_common_ancestor(const CentroidPathDecomposition &cpd, int x, int y) { int cx, px, cy, py; cpd.get(x, cx, px); cpd.get(y, cy, py); while(cx != cy) { if(cpd.depths[*cpd.nodesBegin(cx)] < cpd.depths[*cpd.nodesBegin(cy)]) cpd.go_up(cy, py); else cpd.go_up(cx, px); } return cpd.nodesBegin(cx)[min(px, py)]; } int main() { int N; while(~scanf("%d", &N)) { vector S(N), C(N); rep(i, N) scanf("%d", &S[i]); rep(i, N) scanf("%d", &C[i]); vector g(N); rep(i, N-1) { int A, B; scanf("%d%d", &A, &B), -- A, -- B; g[A].push_back(B); g[B].push_back(A); } CentroidPathDecomposition cpd; cpd.build(g, 0); int N2 = N * 2; coefs.assign(N2, mint()); rep(i, N) coefs[i] = C[cpd.sortednodes[i]]; coefsum.assign(N2 + 1, mint()); rep(i, N2) coefsum[i+1] = coefsum[i] + coefs[i]; vector initval(N); rep(i, N) initval[i] = S[cpd.sortednodes[i]]; SegmentTree segt; segt.init(initval); int Q; scanf("%d", &Q); rep(ii, Q) { int ty; scanf("%d", &ty); if(ty == 0) { int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z), -- X, -- Y; Add add; add.add = Z; int u = X, v = Y; int w = lowest_common_ancestor(cpd, u, v), wc, wp; cpd.get(w, wc, wp); rep(uv, 2) { int c, p; cpd.get(uv == 0 ? u : v, c, p); while(1) { int top = c == wc ? wp + uv : 0; int o = cpd.offsets[c], len = cpd.lengths[c]; //ここで[o + top, o + p]で処理する (閉区間!) segt.addToRange(o + top, o + p + 1, add); if(c == wc) break; cpd.go_up(c, p); } } }else { int X, Y; scanf("%d%d", &X, &Y), -- X, -- Y; int u = X, v = Y; int w = lowest_common_ancestor(cpd, u, v), wc, wp; cpd.get(w, wc, wp); Sum sum; rep(uv, 2) { int c, p; cpd.get(uv == 0 ? u : v, c, p); while(1) { int top = c == wc ? wp + uv : 0; int o = cpd.offsets[c], len = cpd.lengths[c]; //ここで[o + top, o + p]で処理する (閉区間!) sum += segt.getRangeCommutative(o + top, o + p + 1); if(c == wc) break; cpd.go_up(c, p); } } mint ans = sum.sum; printf("%d\n", ans.get()); } } } return 0; }