#include #ifdef DEBUG #include #else #define dump(...) ((void)0) #endif template bool chmin(T &a, const U &b){ return (a > b ? a = b, true : false); } template bool chmax(T &a, const U &b){ return (a < b ? a = b, true : false); } template void fill_array(T (&a)[N], const U &v){ std::fill((U*)a, (U*)(a + N), v); } template auto make_vector(const std::array &a, T value = T()){ static_assert(I >= 1); static_assert(N >= 1); if constexpr (I == 1){ return std::vector(a[N - I], value); }else{ return std::vector(a[N - I], make_vector(a, value)); } } template std::ostream& operator<<(std::ostream &s, const std::vector &a){ for(auto it = a.begin(); it != a.end(); ++it){ if(it != a.begin()) s << " "; s << *it; } return s; } template std::istream& operator>>(std::istream &s, std::vector &a){ for(auto &x : a) s >> x; return s; } /** * @title Modint * @docs mint.md */ namespace haar_lib { template class modint { constexpr static int32_t MOD = M; uint32_t val; public: constexpr static auto mod(){return MOD;} constexpr modint(): val(0){} constexpr modint(int64_t n){ if(n >= M) val = n % M; else if(n < 0) val = n % M + M; else val = n; } constexpr auto& operator=(const modint &a){val = a.val; return *this;} constexpr auto& operator+=(const modint &a){ if(val + a.val >= M) val = (uint64_t)val + a.val - M; else val += a.val; return *this; } constexpr auto& operator-=(const modint &a){ if(val < a.val) val += M; val -= a.val; return *this; } constexpr auto& operator*=(const modint &a){ val = (uint64_t)val * a.val % M; return *this; } constexpr auto& operator/=(const modint &a){ val = (uint64_t)val * a.inv().val % M; return *this; } constexpr auto operator+(const modint &a) const {return modint(*this) += a;} constexpr auto operator-(const modint &a) const {return modint(*this) -= a;} constexpr auto operator*(const modint &a) const {return modint(*this) *= a;} constexpr auto operator/(const modint &a) const {return modint(*this) /= a;} constexpr bool operator==(const modint &a) const {return val == a.val;} constexpr bool operator!=(const modint &a) const {return val != a.val;} constexpr auto& operator++(){*this += 1; return *this;} constexpr auto& operator--(){*this -= 1; return *this;} constexpr auto operator++(int){auto t = *this; *this += 1; return t;} constexpr auto operator--(int){auto t = *this; *this -= 1; return t;} constexpr static modint pow(int64_t n, int64_t p){ if(p < 0) return pow(n, -p).inv(); int64_t ret = 1, e = n % M; for(; p; (e *= e) %= M, p >>= 1) if(p & 1) (ret *= e) %= M; return ret; } constexpr static modint inv(int64_t a){ int64_t b = M, u = 1, v = 0; while(b){ int64_t t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } u %= M; if(u < 0) u += M; return u; } constexpr static auto frac(int64_t a, int64_t b){return modint(a) / modint(b);} constexpr auto pow(int64_t p) const {return pow(val, p);} constexpr auto inv() const {return inv(val);} friend constexpr auto operator-(const modint &a){return modint(M - a.val);} friend constexpr auto operator+(int64_t a, const modint &b){return modint(a) + b;} friend constexpr auto operator-(int64_t a, const modint &b){return modint(a) - b;} friend constexpr auto operator*(int64_t a, const modint &b){return modint(a) * b;} friend constexpr auto operator/(int64_t a, const modint &b){return modint(a) / b;} friend std::istream& operator>>(std::istream &s, modint &a){s >> a.val; return s;} friend std::ostream& operator<<(std::ostream &s, const modint &a){s << a.val; return s;} template static auto div(){ static auto value = inv(N); return value; } explicit operator int32_t() const noexcept {return val;} explicit operator int64_t() const noexcept {return val;} }; } /** * @title Basic graph * @docs graph.md */ namespace haar_lib { template struct edge { int from, to; T cost; int index = -1; edge(){} edge(int from, int to, T cost): from(from), to(to), cost(cost){} edge(int from, int to, T cost, int index): from(from), to(to), cost(cost), index(index){} }; template struct graph { using weight_type = T; using edge_type = edge; std::vector>> data; auto& operator[](size_t i){return data[i];} const auto& operator[](size_t i) const {return data[i];} auto begin() const {return data.begin();} auto end() const {return data.end();} graph(){} graph(int N): data(N){} bool empty() const {return data.empty();} int size() const {return data.size();} void add_edge(int i, int j, T w, int index = -1){ data[i].emplace_back(i, j, w, index); } void add_undirected(int i, int j, T w, int index = -1){ add_edge(i, j, w, index); add_edge(j, i, w, index); } template void read(int M){ for(int i = 0; i < M; ++i){ int u, v; std::cin >> u >> v; u -= I; v -= I; T w = 1; if(WEIGHTED) std::cin >> w; if(DIRECTED) add_edge(u, v, w, i); else add_undirected(u, v, w, i); } } }; template using tree = graph; } /** * @title Heavy-light decomposition * @docs heavy_light_decomposition.md */ namespace haar_lib { template class hl_decomposition { int n; std::vector sub, // subtree size par, // parent id head, // chain head id id, // id[original id] = hld id rid, // rid[hld id] = original id next, // next node in a chain end; // int dfs_sub(tree &tr, int cur, int p){ par[cur] = p; int t = 0; for(auto &e : tr[cur]){ if(e.to == p) continue; sub[cur] += dfs_sub(tr, e.to, cur); if(sub[e.to] > t){ t = sub[e.to]; next[cur] = e.to; std::swap(e, tr[cur][0]); } } return sub[cur]; } void dfs_build(const tree &tr, int cur, int &i){ id[cur] = i; rid[i] = cur; ++i; for(auto &e : tr[cur]){ if(e.to == par[cur]) continue; head[e.to] = (e.to == tr[cur][0].to ? head[cur] : e.to); dfs_build(tr, e.to, i); } end[cur] = i; } public: hl_decomposition(tree tr, int root): n(tr.size()), sub(n, 1), par(n, -1), head(n), id(n), rid(n), next(n, -1), end(n, -1){ dfs_sub(tr, root, -1); int i = 0; dfs_build(tr, root, i); } std::vector> path_query_vertex(int x, int y) const { std::vector> ret; const int w = lca(x, y); { int y = w; bool d = true; while(1){ if(id[x] > id[y]) std::swap(x, y), d = not d; int l = std::max(id[head[y]], id[x]), r = id[y] + 1; if(l != r) ret.emplace_back(l, r, d); if(head[x] == head[y]) break; y = par[head[y]]; } } x = y; y = w; { std::vector> temp; bool d = false; while(1){ if(id[x] > id[y]) std::swap(x, y), d = not d; int l = std::max({id[head[y]], id[x], id[w] + 1}), r = id[y] + 1; if(l != r) temp.emplace_back(l, r, d); if(head[x] == head[y]) break; y = par[head[y]]; } std::reverse(temp.begin(), temp.end()); ret.insert(ret.end(), temp.begin(), temp.end()); } return ret; } std::vector> path_query_edge(int x, int y) const { std::vector> ret; while(1){ if(id[x] > id[y]) std::swap(x, y); if(head[x] == head[y]){ if(x != y) ret.emplace_back(id[x] + 1, id[y] + 1); break; } ret.emplace_back(id[head[y]], id[y] + 1); y = par[head[y]]; } return ret; } std::pair subtree_query_edge(int x) const { return {id[x] + 1, end[x]}; } std::pair subtree_query_vertex(int x) const { return {id[x], end[x]}; } int get_edge_id(int u, int v) const { // 辺に対応するid if(par[u] == v) return id[u]; if(par[v] == u) return id[v]; return -1; } int parent(int x) const {return par[x];}; int lca(int u, int v) const { while(1){ if(id[u] > id[v]) std::swap(u, v); if(head[u] == head[v]) return u; v = par[head[v]]; } } int get_id(int x) const { return id[x]; } }; } namespace haar_lib { template class lazy_segment_tree_with_coefficients { const int depth, size, hsize; std::vector data, lazy, coeff; void propagate(int i){ if(lazy[i] == 0) return; if(i < hsize){ lazy[i << 1 | 0] = lazy[i] + lazy[i << 1 | 0]; lazy[i << 1 | 1] = lazy[i] + lazy[i << 1 | 1]; } data[i] = data[i] + lazy[i] * coeff[i]; lazy[i] = 0; } T update(int i, int l, int r, int s, int t, const T &x){ propagate(i); if(r <= s || t <= l) return data[i]; if(s <= l && r <= t){ lazy[i] += x; propagate(i); return data[i]; } return data[i] = update(i << 1 | 0, l, (l + r) / 2, s, t, x) + update(i << 1 | 1, (l + r) / 2, r, s, t, x); } T get(int i, int l, int r, int x, int y){ propagate(i); if(r <= x || y <= l) return 0; if(x <= l && r <= y) return data[i]; return get(i << 1 | 0, l, (l + r) / 2, x, y) + get(i << 1 | 1, (l + r) / 2, r, x, y); } public: lazy_segment_tree_with_coefficients(){} lazy_segment_tree_with_coefficients(int n, std::vector coeff_): depth(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1), size(1 << depth), hsize(size / 2), data(size, 0), lazy(size, 0), coeff(size, 0) { for(int i = hsize; i < size; ++i) coeff[i] = coeff_[i - hsize]; for(int i = hsize; --i >= 1;) coeff[i] = coeff[i << 1 | 0] + coeff[i << 1 | 1]; } void update(int l, int r, const T &x){update(1, 0, hsize, l, r, x);} void update_at(int i, const T &x){update(i, i + 1, x);} T get(int l, int r){return get(1, 0, hsize, l, r);} T operator[](int i){return get(i, i + 1);} void init(const T &val){ init_with_vector(std::vector(hsize, val)); } void init_with_vector(const std::vector &val){ data.assign(size, 0); lazy.assign(size, 0); for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i]; for(int i = hsize; --i >= 0;) data[i] = data[i << 1 | 0] + data[i << 1 | 1]; } }; } /** * @docs sort_simultaneously.md */ namespace haar_lib { template void sort_simultaneously(const Compare &compare, std::vector &... args){ const int N = std::max({args.size() ...}); std::vector ord(N); std::iota(ord.begin(), ord.end(), 0); std::sort(ord.begin(), ord.end(), compare); (void)std::initializer_list{ (void( [&](){ auto temp = args; for(int i = 0; i < N; ++i) temp[i] = args[ord[i]]; std::swap(temp, args); }() ), 0) ...}; } } namespace haar_lib {} namespace solver { using namespace haar_lib; constexpr int m1000000007 = 1000000007; constexpr int m998244353 = 998244353; void init(){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(12); std::cerr << std::fixed << std::setprecision(12); std::cin.exceptions(std::ios_base::failbit); } using mint = modint; void solve(){ int N; std::cin >> N; std::vector S(N); std::cin >> S; std::vector C(N); std::cin >> C; tree tr(N); tr.read<1, false, false>(N - 1); auto hld = hl_decomposition(tr, 0); sort_simultaneously([&](int i, int j){return hld.get_id(i) < hld.get_id(j);}, S, C); auto seg = lazy_segment_tree_with_coefficients(N, C); seg.init_with_vector(S); int Q; std::cin >> Q; while(Q--){ int type; std::cin >> type; if(type == 0){ int X, Y, Z; std::cin >> X >> Y >> Z; --X, --Y; for(auto [l, r, d] : hld.path_query_vertex(X, Y)){ seg.update(l, r, Z); } }else{ int X, Y; std::cin >> X >> Y; --X, --Y; mint ans = 0; for(auto [l, r, d] : hld.path_query_vertex(X, Y)){ ans += seg.get(l, r); } std::cout << ans << "\n"; } } } } int main(){ solver::init(); while(true){ try{ solver::solve(); }catch(const std::istream::failure &e){ break; } } return 0; }