#include using namespace std; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #define all(x) x.begin(),x.end() long long inv_mod(long long a, long long m) { long long b, x, u, q, abs_m, tmp; abs_m = (m < 0) ? -m : m; b = m; x = 1; u = 0; while (b > 0) { q = a / b; tmp = u; u = x - q * u; x = tmp; tmp = b; b = a - q * b; a = tmp; } return (x < 0) ? abs_m + x : x; } template struct ModInt{ long long value; ModInt(long long n = 0) : value(n % MOD){} operator long long() const noexcept {return value % MOD;} ModInt operator++(int){ ModInt before = *this; value = (value + 1) % MOD; return before; } ModInt operator--(int){ ModInt before = *this; value = (value - 1 + MOD) % MOD; return before; } ModInt& operator++(){ value = (value + 1) % MOD; return *this; } ModInt& operator--(){ value = (value - 1 + MOD) % MOD; return *this; } bool operator!() const noexcept{ return !static_cast(value); } ModInt operator+() const{ return value; } ModInt operator-() const{ return (-value + MOD) % MOD; } ModInt& operator*=(const ModInt& m){ return *this = ModInt((this->value * m.value) % MOD); } ModInt& operator+=(const ModInt& m){ return *this = ModInt((this->value + m.value) % MOD); } ModInt& operator-=(const ModInt& m){ return *this = ModInt((this->value - m.value + MOD) % MOD); } ModInt& operator/=(const ModInt& m){ return *this = ModInt((this->value * inv_mod(m.value,MOD)) % MOD); } }; template ModInt operator*(const ModInt& m1,const ModInt& m2){return ModInt(m1) *= m2;} template ModInt operator+(const ModInt& m1,const ModInt& m2){return ModInt(m1) += m2;} template ModInt operator-(const ModInt& m1,const ModInt& m2){return ModInt(m1) -= m2;} template ModInt operator/(const ModInt& m1,const ModInt& m2){return ModInt(m1) /= m2;} template ModInt operator*(const long long& m1,const ModInt& m2){return ModInt(m1) *= m2;} template ModInt operator+(const long long& m1,const ModInt& m2){return ModInt(m1) += m2;} template ModInt operator-(const long long& m1,const ModInt& m2){return ModInt(m1) -= m2;} template ModInt operator/(const long long& m1,const ModInt& m2){return ModInt(m1) /= m2;} /* include file*/ #include #include using namespace std; template struct LazySegment { using Func = function; vector node; vector lazy; vector ls; vector lazyFlag; int n; Monoid ide; Monoid lazy_init; Monoid func(Monoid a,Monoid b){ return a + b; } Monoid lazy_make(int l,int r,Monoid x,Monoid lazy){ return lazy + x; } Monoid lazy_effect(Monoid node,Monoid lazy,int k){ return node + lazy * ls[k]; } Monoid lazy_throw(Monoid from,Monoid to){ return to + from; } LazySegment(const vector init, Monoid ide_, Monoid lazy_i) : ide(ide_), lazy_init(lazy_i) { n = 1; int sz = init.size(); while (n < sz) n *= 2; node.resize(n * 2 - 1, ide); lazy.resize(n * 2 - 1, lazy_init); lazyFlag.resize(n * 2 - 1, false); for (int i = 0; i < sz; i++) node[i + n - 1] = init[i]; for (int i = n - 2; i >= 0; i--) node[i] = func(node[i * 2 + 1], node[i * 2 + 2]); } void eval(int k, int l, int r) { if (lazyFlag[k]) { node[k] = lazy_effect(node[k], lazy[k],k); if (r - l > 1) { lazy[2 * k + 1] = lazy_throw(lazy[k], lazy[2 * k + 1]); lazy[2 * k + 2] = lazy_throw(lazy[k], lazy[2 * k + 2]); lazyFlag[2 * k + 1] = true; lazyFlag[2 * k + 2] = true; } lazyFlag[k] = false; lazy[k] = lazy_init; } } void update_inter(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = lazy_make(l, r, x, lazy[k]); lazyFlag[k] = true; eval(k, l, r); } else { update_inter(a, b, x, k * 2 + 1, l, (l + r) / 2); update_inter(a, b, x, k * 2 + 2, (l + r) / 2, r); node[k] = func(node[k * 2 + 1], node[k * 2 + 2]); } } Monoid get_inter(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (r <= a || b <= l) return ide; if (a <= l && r <= b) return node[k]; Monoid lm = get_inter(a, b, k * 2 + 1, l, (l + r) / 2); Monoid rm = get_inter(a, b, k * 2 + 2, (l + r) / 2, r); return func(lm, rm); } }; const long long mm = 1e9 + 7; using Int = ModInt; #include #include #include #include using namespace std; using i64 = long long; struct HLDecomposition{ int n,pos; vector > G; vector vid,head,hvy,par,dep,inv,sub; LazySegment seg; HLDecomposition(int sz): n(sz),pos(0),G(n), vid(n,-1),head(n),hvy(n,-1), par(n),dep(n),inv(n),sub(n,1),seg(vector(0),0,0){} void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } void dfs(int rt){ typedef pair T; stack st; par[rt] = -1; dep[rt] = 0; st.push(make_pair(rt,0)); while(!st.empty()){ int v= st.top().first; int &i = st.top().second; if(i < (int)G[v].size()){ int u = G[v][i++]; if(u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.push(make_pair(u,0)); } else{ st.pop(); int res = 0; for(int i = 0;i < (int)G[v].size();i++){ int u = G[v][i]; if(u == par[v]) continue; sub[v] += sub[u]; if(res < sub[u]) res = sub[u],hvy[v] = u; } } } } void bfs(int r){ int &k = pos; queue q; q.push(r); while(!q.empty()){ int h = q.front(); q.pop(); for(int i = h;i != -1;i = hvy[i]){ vid[i] = k++; inv[vid[i]] = i; head[i] = h; for(int j = 0;j < (int)G[i].size();j++){ int u = G[i][j]; if(u != par[i] && u != hvy[i]) q.push(u); } } } } void build(int r){ dfs(r); bfs(r); } void f(int l,int r,i64 z){ seg.update_inter(l,r + 1,z); } i64 f2(int l,int r){ return seg.get_inter(l,r + 1); } void for_vertex(int u,int v,i64 z){ while(1){ if(vid[u] > vid[v]) swap(u,v); f(max(vid[head[v]],vid[u]),vid[v],z); if(head[u] != head[v]) v= par[head[v]]; else break; } } i64 for_vertex2(int u,int v){ i64 sum = 0; while(1){ if(vid[u] > vid[v]) swap(u,v); sum += f2(max(vid[head[v]],vid[u]),vid[v]); if(head[u] != head[v]) v= par[head[v]]; else break; } return sum; } int lca(int u,int v){ while(1){ if(vid[u] > vid[v]) swap(u,v); if(head[u] == head[v]) return u; v = par[head[v]]; } } int distance(int u,int v){ return dep[u] + dep[v] - 2 * dep[lca(u,v)]; } }; int N; vector S,C; int main(){ cin >> N; S.resize(N); C.resize(N); rep(i,0,N - 1) cin >> S[i]; rep(i,0,N - 1) cin >> C[i]; HLDecomposition hld(N); rep(i,0,N -2){ int a,b; cin >> a >> b; a--; b--; hld.add_edge(a,b); } hld.build(0); int Q; cin >> Q; vector ans; vector s(N); vector c(N); rep(i,0,N - 1){ s[hld.vid[i]] = S[i]; c[hld.vid[i]] = C[i]; } hld.seg = LazySegment(s,0,0); { LazySegment seg(c,0,0); hld.seg.ls = seg.node; } rep(i,0,Q - 1){ int t; cin >> t; if(t == 0){ i64 x,y,z; cin >> x >> y >> z; x--; y--; hld.for_vertex(x,y,z); } else{ i64 x,y; cin >> x >> y; x--; y--; ans.push_back(hld.for_vertex2(x,y)); } } for(int i = 0;i < ans.size();i++){ cout << ans[i] << endl; } return 0; }