#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include using namespace std; const int mod = 1e9 + 7; uint32_t inv; int r2; int freq[32]; int reduce(uint64_t x) { uint64_t y = uint64_t(uint32_t(x) * inv) * mod; return int(x >> 32) + mod - int(y >> 32); } int transform(int n) { return reduce(int64_t(n) * r2); } int normalize(int n) { return n >= mod ? n - mod : n; } void init_montgomery_reduction() { inv = 1; for (int i = 0; i < 5; ++i) inv *= 2 - inv * uint32_t(mod); r2 = -uint64_t(mod) % mod; } void add(int &a, int b) { (a += b - mod) < 0 ? a += mod : a; } int modadd(int a, int b) { return (a += b - mod) < 0 ? a + mod : a; } int modmul(int a, int b) { return reduce(int64_t(a) * b); } const int N = 1 << 18; struct node { int w, sum, add; }; node seg[N * 2]; int naive[N], ww[N]; int S[N], C[N]; void push(int k) { if (seg[k].add == 0) return; add(seg[k].sum, modmul(seg[k].add, seg[k].w)); add(seg[k * 2 + 0].add, seg[k].add); add(seg[k * 2 + 1].add, seg[k].add); seg[k].add = 0; } int get_val(int k) { if (seg[k].add == 0) return seg[k].sum; return modadd(seg[k].sum, modmul(seg[k].add, seg[k].w)); } void update(int l, int r, int v, int H) { if (H >= 6) { int ll = l + N; int rr = r + N - 1; bool L = false; bool R = false; for (l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l & 1) add(seg[l++].add, v), L = true; if (r & 1) add(seg[--r].add, v), R = true; } for (int i = 1; i <= H; i++) { seg[ll >> 1].sum = modadd(get_val(ll), get_val(ll ^ 1)); if (R && ll != rr) { seg[rr >> 1].sum = modadd(get_val(rr), get_val(rr ^ 1)); } ll >>= 1; rr >>= 1; } } else if (r - l >= 16) { const int M = 4; while (l < r && (l & 0x3) != 0) add(naive[l], modmul(ww[l], v)), l++; while (l < r && (r & 0x3) != 0) r--, add(naive[r], modmul(ww[r], v)); for (int i = l; i < r; i += 4) { for (int j = 0; j < M; j++) { add(naive[i + j], modmul(ww[i + j], v)); } } } else { for (int i = l; i < r; i++) { add(naive[i], modmul(ww[i], v)); } } } int query(int l, int r, int H) { if (H >= 6) { int ll = l + N; int rr = r + N - 1; for (int i = H; i >= 1; i--) { push(ll >> i); if (ll >> i != rr >> i) push(rr >> i); } int res = 0; for (l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l & 1) add(res, get_val(l++)); if (r & 1) add(res, get_val(--r)); } return res; } else if (r - l >= 16) { const int M = 4; int res = 0; while (l < r && (l & 0x3) != 0) add(res, naive[l]), l++; while (l < r && (r & 0x3) != 0) r--, add(res, naive[r]); for (int i = l; i < r; i += 4) { for (int j = 0; j < M; j++) { add(res, naive[i + j]); } } return res; } else { int res = 0; for (int i = l; i < r; i++) { add(res, naive[i]); } return res; } } struct HLDecomposition { struct node { int vid, head, parent, len_path = 0; }; vector> g; vector heavy; vector vs; HLDecomposition(int n) : g(n), vs(n), heavy(n) {} void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); } int dfs(int curr, int prev) { vs[curr].parent = prev; heavy[curr] = -1; int sub = 1, max_sub = 0; for (int next : g[curr]) if (next != prev) { int sub_next = dfs(next, curr); sub += sub_next; if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; } return sub; } void bfs() { int k = 0; queue q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { vs[h].len_path++; vs[i].vid = k++; vs[i].head = h; for (int j : g[i]) if (j != vs[i].parent && j != heavy[i]) q.push(j); } vs[h].len_path = log2(vs[h].len_path * 2 - 1); freq[vs[h].len_path]++; } } void update_path(int u, int v, int z) { while (true) { if (vs[u].vid > vs[v].vid) swap(u, v); int uh = vs[u].head; int vh = vs[v].head; if (uh == vh) { update(vs[u].vid, vs[v].vid + 1, z, vs[vh].len_path); break; } else { update(vs[vh].vid, vs[v].vid + 1, z, vs[vh].len_path); v = vs[vh].parent; } } } int query_path(int u, int v) { int res = 0; while (true) { if (vs[u].vid > vs[v].vid) swap(u, v); int uh = vs[u].head; int vh = vs[v].head; if (vs[u].head == vs[v].head) { ::add(res, query(vs[u].vid, vs[v].vid + 1, vs[vh].len_path)); break; } else { ::add(res, query(vs[vh].vid, vs[v].vid + 1, vs[vh].len_path)); v = vs[vh].parent; } } return res; } int operator[](int k) { return vs[k].vid; } }; // 入出力。Min_25 さんのコードを参考にしました #define getchar getchar_unlocked #define putchar putchar_unlocked // - 0.30 sec int in() { int n, c; while ((c = getchar()) < '0') if (c == EOF) return -1; n = c - '0'; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } int in_t() { return transform(in()); } // - 0.02 sec void put_int(int n) { int res[11], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } double elapsed() { static clock_t curr; clock_t prev = curr; curr = clock(); return (double)(curr - prev) / CLOCKS_PER_SEC; } int main() { init_montgomery_reduction(); int n = in(); for (int i = 0; i < n; i++) S[i] = in_t(); for (int i = 0; i < n; i++) C[i] = in_t(); HLDecomposition hld(n); for (int i = 1; i < n; i++) hld.add(in() - 1, in() - 1); hld.build(); for (int i = 0; i < n; i++) { seg[hld[i] + N].sum = S[i]; seg[hld[i] + N].w = C[i]; naive[hld[i]] = S[i]; ww[hld[i]] = C[i]; } for (int i = N - 1; i >= 1; i--) { seg[i].sum = modadd(seg[i * 2 + 0].sum, seg[i * 2 + 1].sum); seg[i].w = modadd(seg[i * 2 + 0].w, seg[i * 2 + 1].w); } for (int i = 0; i < 32; i++) { cerr << i << " " << freq[i] << endl; } int q = in(); while (q--) { int t = in(); if (t == 0) { int u = in() - 1, v = in() - 1, z = in_t(); hld.update_path(u, v, z); } else { int u = in() - 1, v = in() - 1; put_int(normalize(reduce(hld.query_path(u, v)))); } } }