#include using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);++i) #define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() #define valid(y,x,h,w) (0<=y&&y pii; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (bbasic_ostream& operator<<(basic_ostream&os, const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';} templateostream&operator<<(ostream &o,const pair&t){return o<<'('<void output(ostream&,const Tp&){} templatevoid output(ostream &o,const Tp&t){if(N)o<<',';o<(t);output(o,t);} templateostream&operator<<(ostream&o,const tuple&t){o<<'(';output<0,tuple,Ts...>(o,t);return o<<')';} templatevoid output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20]; int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);} templatevoid outputs(T t){output(t);} templatevoid outputs(S a,T...t){output(a,32);outputs(t...);} templatevoid output(T *a,int n){REP(i,n)cout<void output(T *a,int n,int m){REP(i,n)output(a[i],m);} templatebool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;); if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;} templatebool input(S&a,T&...t){input(a);return input(t...);} templatebool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;} #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) #define tenll(x) ((ll)1e##x) class LCA { public: const vector>& e; int V, logV; vector depth; vector > parent; LCA(const vector>& e) : e(e) { this->V = sz(e); logV = 0; while (V >= (1 << logV)) logV++; this->depth = vector(V); this->parent = vector >(logV, vector(V)); dfs(0, -1, 0); build(); } void dfs(int v, int par, int d) { depth[v] = d; parent[0][v] = par; for (auto to : e[v]) { if (par == to) continue; dfs(to, v, d + 1); } } void build() { for (int k = 0; k + 1 < logV; 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]]; } } } int query(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < logV; k++) { if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; } if (u == v) return u; for (int k = logV - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; template struct ModInt { int x; ModInt() : x(0) {} ModInt(ll s) { if ((x = s % MOD) < 0) x += MOD; } ModInt operator+=(ModInt rhs) { if ((x+=rhs.x) >= MOD) x -= MOD; return *this; } ModInt operator-=(ModInt rhs) { if ((x-=rhs.x) < 0) x += MOD; return *this; } ModInt operator*=(ModInt rhs) { x = (ll)x*rhs.x % MOD; return *this; } ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; } ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; } ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; } ModInt operator/=(ModInt rhs) { static const ll inv2 = ModInt(2).inv().x; // 2で割るのは特別に保存してみる ll i = (rhs.x == 2 ? inv2 : rhs.inv().x); x = x*i%MOD; return *this; } ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; } ModInt inv() { return pow(MOD-2); } ModInt pow(ll n) const { ModInt r = 1, t = x; for (;n;n>>=1,t*=t) if (n&1) r *= t; return r; } static ModInt strnum(const string &n) {ModInt a = 0; for (char c:n) a = a*10+c-'0'; return a;} friend ostream& operator<<(ostream &os, const ModInt rhs){ return os << rhs.x; } }; typedef ModInt mint; struct Data { mint csum; mint val; void init(int l, int s, int c) { // 末端ノードの初期化 val = s; csum = c; } void change(mint v) { // ノードの値を変える val += v; } void combine(const Data &l, const Data &r) { // 区間の統合 val = l.val + r.val; csum = l.csum + r.csum; } string str() { stringstream ss; ss << val; return ss.str(); } }; struct Param { mint z; Param() {init();} void init() { z = 0; } void update(const Param &pp) { // pp : 親のParam // 今のthisにさらにppが適用された場合にthisがどうなるか z += pp.z; } void update(int _z, int l, int r) { z += _z; } void apply(Data &d, int l, int r) const { // 区間に関するクエリに答えなければならないときは // ここの適用を効率的にできるかが鍵 mint v = d.csum * z; d.change(v); } }; struct SegTree { int l,r; // 区間の範囲 int mid; SegTree *cl, *cr; Param param; Data d; SegTree(int l, int r, const vector &s, const vector &c) : l(l), r(r) { mid = (l+r)>>1; if (l+1 == r) { d.init(l,s[l],c[l]); } else { cl = new SegTree(l,mid,s,c); cr = new SegTree(mid,r,s,c); d.combine(cl->d,cr->d); } } void change(int k, int v) { if (l+1 == r) { d.change(v); } else { down(); if (k < mid) cl->change(k,v); else cr->change(k,v); d.combine(cl->d,cr->d); } } Data query(int L, int R) { if (L<=l && r<=R) return d; down(); if (R<=mid) return cl->query(L,R); if (L>=mid) return cr->query(L,R); Data res; res.combine(cl->query(L,R), cr->query(L,R)); return res; } void down() { cl->update(param); cr->update(param); cl->param.update(param); cr->param.update(param); param.init(); } void update(const Param &par) { par.apply(d, l, r); } void apply(int L, int R, int z) { if (L<=l && r<=R) { param.update(z,L,R); // ここでは今回分のみ自分に適用する必要がある. Param par; par.update(z,L,R); par.apply(d,l,r); return; } down(); if (Lapply(L,R,z); if (R>mid) cr->apply(L,R,z); d.combine(cl->d,cr->d); } void print(bool f = 1) { if (l+1 == r) { cout << d.str() << " "; return; } down(); cl->print(0); cr->print(0); if (f) cout << endl; } }; class RangeTree { public: int n; vector> dat; RangeTree(vector& a) { n = 1; while (n < sz(a)) n <<= 1; dat.resize(2 * n - 1); REP(i, n) { int k = n - 1 + i; if (i < sz(a)) dat[k].push_back(a[i]); else dat[k].push_back(ten(8)); } for (int i = n - 2; i >= 0; i--) { dat[i].resize(sz(dat[2 * i + 1]) + sz(dat[2 * i + 2])); merge(dat[2 * i + 1].begin(), dat[2 * i + 1].end(), dat[2 * i + 2].begin(), dat[2 * i + 2].end(), dat[i].begin()); } } int query(int l, int r, int val) { return query(l, r, val, 0, 0, n); } int query(int l, int r, int val, int k, int a, int b) { if (r <= a || b <= l) return 0; if (l <= a && b <= r) { return lower_bound(dat[k].begin(), dat[k].end(), val + 1) - dat[k].begin(); } return query(l, r, val, 2 * k + 1, a, (a + b) / 2) + query(l, r, val, 2 * k + 2, (a + b) / 2, b); } }; //heavy-light decomposition class HL_decomposition { public: const vector>& e; const int n; vector par, depth, ord; //親,深さ、トポロジカルソート vector cluster; //decompositionした結果どのクラスタに属するか vector > pathes; //各クラスタの、上から下へのパス vector path_idx; // path_idx[v] = 上記パスでのindex void init(int v) { depth.resize(n, 0); par.resize(n, 0); ord.resize(n, 0); depth[v] = 0; par[v] = -1; ord[0] = v; //ordをキューとして使い、bfsする for (int p = 0, r = 1; p < r; p++) { int cur = ord[p]; for (int nv : e[cur]) { if (nv == par[cur]) continue; ord[r++] = nv; par[nv] = cur; depth[nv] = depth[cur] + 1; } } } void decomposition() { vector subtree_size(n, 1); for (int i = n - 1; i > 0; i--) subtree_size[par[ord[i]]] += subtree_size[ord[i]]; cluster.resize(n, -1); int cluster_type = 0; REP(i, n) { int u = ord[i]; if (cluster[u] == -1) cluster[u] = cluster_type++; int max_subsize = -1, selected = -1; for (int v : e[u]) { if (par[u] != v && max_subsize < subtree_size[v]) { max_subsize = subtree_size[v]; selected = v; } } if (selected != -1) cluster[selected] = cluster[u]; } } void enum_pathes() { int cluster_num = 0; vector rp(n); REP(i, n) { rp[cluster[i]]++; cluster_num = max(cluster_num, cluster[i]); } cluster_num++; pathes.resize(cluster_num); REP(i, cluster_num) pathes[i].resize(rp[i]); for (int i = n - 1; i >= 0; i--) { int u = ord[i]; pathes[cluster[u]][--rp[cluster[u]]] = u; } } void set_path_idx() { path_idx.resize(n); for (const vector& path : pathes) { REP(i, sz(path)) path_idx[path[i]] = i; } } public: HL_decomposition(const vector>& e) : e(e), n(sz(e)) { init(0); decomposition(); enum_pathes(); set_path_idx(); } }; // exsample of how to use class tree_query { LCA* lca; HL_decomposition *hl; vector rts; int mx; public: tree_query(vector>& e, vector& s, vector& c) { lca = new LCA(e); hl = new HL_decomposition(e); rts.resize(sz(hl->pathes)); REP(i, sz(rts)) { vector cs, ss; for (int v : hl->pathes[i]) { ss.push_back(s[v]); cs.push_back(c[v]); } rts[i] = new SegTree(0, cs.size(), ss, cs); } } void update(int v, int z) { while (v != -1) { rts[hl->cluster[v]]->apply(0, hl->path_idx[v] + 1, z); v = hl->par[hl->pathes[hl->cluster[v]][0]]; } } void update(int u, int v, int z) { int p = lca->query(u, v); update(u,z); update(v,z); update(p,-z); if (lca->parent[0][p] != -1) update(lca->parent[0][p],-z); } mint count(int v) { mint ret = 0; while (v != -1) { ret += rts[hl->cluster[v]]->query(0, hl->path_idx[v] + 1).val; v = hl->par[hl->pathes[hl->cluster[v]][0]]; } return ret; } mint query(int u, int v) { int p = lca->query(u, v); mint a1 = count(u); mint a2 = count(v); mint a3 = count(p); mint a4 = lca->parent[0][p] != -1 ? count(lca->parent[0][p]) : 0; mint cnt = a1 + a2 - a3 - a4; return cnt; } ~tree_query() { delete lca; delete hl; REP(i, sz(rts)) delete rts[i]; } }; int main() { int n; cin >> n; vector s(n), c(n); vector> e(n); REP(i, n) cin >> s[i]; REP(i, n) cin >> c[i]; REP(i, n-1) { int a, b; cin >> a >> b; a--; b--; e[a].push_back(b); e[b].push_back(a); } tree_query tq(e, s, c); int q; cin >> q; REP(i, q) { int t; input(t); if (t == 0) { int x, y, z; input(x,y,z); x--;y--; tq.update(x, y, z); } else { int x, y; input(x,y); x--;y--; mint res = tq.query(x, y); output(res.x); } } }