#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; struct mint { int x; mint() : x(0) {} mint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} mint& operator+=(const mint& p){ if((x += p.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& p){ if((x -= p.x) < 0) x += mod; return *this; } mint& operator*=(const mint& p){ x = (int)(1LL * x * p.x % mod); return *this; } mint& operator/=(const mint& p){ *this *= p.inverse(); return *this; } mint operator-() const { return mint(-x); } mint operator+(const mint& p) const { return mint(*this) += p; } mint operator-(const mint& p) const { return mint(*this) -= p; } mint operator*(const mint& p) const { return mint(*this) *= p; } mint operator/(const mint& p) const { return mint(*this) /= p; } bool operator==(const mint& p) const { return x == p.x; } bool operator!=(const mint& p) const { return x != p.x; } mint pow(int64_t n) const { mint res = 1, mul = x; while(n > 0){ if(n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } // x^(a^b) // warning : x と mod は互いに素 // x != 0 かつ x % mod == 0 かつ a > 0 はこれを呼び出さずに 0 を返すように処理 mint pow2(int64_t a, int64_t b) const { if(b == 0) return *this; if((a %= mod - 1) == 0) return mint(1); int64_t n = 1; while(b > 0){ if(b & 1) (n *= a) %= mod - 1; (a *= a) %= mod - 1; b >>= 1; } return pow(n); } mint inverse() const { return pow(mod - 2); } friend ostream& operator<<(ostream& os, const mint& p){ return os << p.x; } friend istream& operator>>(istream& is, mint& p){ int64_t val; is >> val; p = mint(val); return is; } }; struct HeavyLightDecomposition { using Graph = vector>; int V; Graph& g; vector subtree_size, head, in, out, par, inverse; HeavyLightDecomposition(Graph& g_) : V(g_.size()), g(g_), subtree_size(V), head(V), in(V), out(V), par(V), inverse(V) {} void calc_subtree_size(int cur, int p){ if(g[cur].size() && g[cur][0] == p){ swap(g[cur][0], g[cur].back()); } subtree_size[cur] = 1; par[cur] = p; for(auto& child : g[cur]){ if(child == p) continue; calc_subtree_size(child, cur); subtree_size[cur] += subtree_size[child]; if(subtree_size[g[cur][0]] < subtree_size[child]){ swap(g[cur][0], child); } } } void dfs(int cur, int p, int& times){ in[cur] = times++; inverse[in[cur]] = cur; for(auto& child : g[cur]){ if(child == p) continue; head[child] = (g[cur][0] == child ? head[cur] : child); dfs(child, cur, times); } out[cur] = times; } void build(int root = 0){ calc_subtree_size(root, -1); int t = 0; dfs(root, -1, t); } int get(int v, int k){ for(;;){ int u = head[v]; if(in[v] - k >= in[u]){ // u, v in same group return inverse[in[v] - k]; } k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v){ for(;; v = par[head[v]]){ if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; } } vector> get_sections(int u, int v, bool is_edge = false){ vector> res; for(;; v = par[head[v]]){ if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; res.emplace_back(in[head[v]], in[v] + 1); } res.emplace_back(in[u] + is_edge, in[v] + 1); return res; } int operator[](const int& v) const { return in[v]; } int edge(int u, int v){ return in[in[u] > in[v] ? u : v]; } }; template struct LazySegmentTree{ using F = function; using G = function; using H = function; int sz; vector data; vector lazy; const F f; const G g; const H h; const Monoid M1; // モノイドの単位元 const OperatorMonoid OM0; // 作用素モノイドの単位元 LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; while(sz < n) sz <<= 1; data.assign(sz << 1, M1); lazy.assign(sz << 1, OM0); } void set(int k, const Monoid &x){ data[k + sz] = x; } void build(){ for(int k = sz - 1; k > 0; --k){ data[k] = f(data[k << 1], data[k << 1 | 1]); } } void propagate(int k){ if(lazy[k] != OM0){ if(k < sz){ lazy[k << 1] = h(lazy[k << 1], lazy[k]); lazy[k << 1 | 1] = h(lazy[k << 1 | 1], lazy[k]); } data[k] = g(data[k], lazy[k]); lazy[k] = OM0; } } Monoid update(int a, int b, const OperatorMonoid &x, int k = 1, int l = 0, int r = -1){ if(r == -1) r = sz; propagate(k); if(r <= a || b <= l) return data[k]; else if(a <= l && r <= b){ lazy[k] = h(lazy[k], x); propagate(k); return data[k]; } else{ return data[k] = f(update(a, b, x, k << 1, l, (l + r) >> 1), update(a, b, x, k << 1 | 1, (l + r) >> 1, r)); } } Monoid query(int a, int b, int k = 1, int l = 0, int r = -1){ if(r == -1) r = sz; propagate(k); if(r <= a || b <= l) return M1; else if(a <= l && r <= b) return data[k]; else{ return f(query(a, b, k << 1, l, (l + r) >> 1), query(a, b, k << 1 | 1, (l + r) >> 1, r)); } } Monoid operator[](const int &i){ int k = 1, l = 0, r = sz, m; while(k < sz){ propagate(k); k <<= 1; m = (l + r) >> 1; if(i + 1 <= m) r = m; else { l = m; ++k; } } propagate(k); return data[k]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N; vector S(N), C(N); for(int i = 0; i < N; ++i) cin >> S[i]; for(int i = 0; i < N; ++i) cin >> C[i]; vector> g(N); for(int i = 1; i < N; ++i){ int u, v; cin >> u >> v; --u, --v; g[u].emplace_back(v); g[v].emplace_back(u); } HeavyLightDecomposition hld(g); hld.build(); using Node = pair; auto op = [&](Node l, Node r) -> Node { return {l.first + r.first, l.second + r.second}; }; auto mapping = [&](Node x, int f) -> Node { return {x.first + x.second * f, x.second}; }; auto composition = [&](int x, int y) -> int { return x + y; }; LazySegmentTree seg(N, op, mapping, composition, {0, 0}, 0); for(int i = 0; i < N; ++i){ seg.set(hld[i], {S[i], C[i]}); } seg.build(); cin >> Q; for(int q = 0; q < Q; ++q){ int t, x, y; cin >> t >> x >> y; --x, --y; auto sections = hld.get_sections(x, y); if(t == 0){ int z; cin >> z; for(auto& [l, r] : sections){ seg.update(l, r, z); } } else{ mint ans = 0; for(auto& [l, r] : sections){ ans += seg.query(l, r).first; } cout << ans << '\n'; } } return 0; }