#include #include #include #include typedef int32_t i32; typedef int64_t i64; #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) const i32 mod = 1000000007; typedef struct graph { i32 *v; i32 *next; i32 *start; i32 n; i32 p; } graph; void init_graph (graph *g) { for (i32 i = 0; i < g->n; ++i) { g->start[i] = -1; } g->p = 0; } graph* new_graph (i32 n, i32 e) { graph *g = ALLOC (1, graph); g->v = ALLOC (e, i32); g->next = ALLOC (e, i32); g->start = ALLOC (n, i32); g->n = n; g->p = 0; init_graph (g); return g; } void add_edge (graph *g, i32 a, i32 b) { i32 p = g->p; g->v[p] = b; g->next[p] = g->start[a]; g->start[a] = p; g->p++; } void dfs_size (i32 v, graph *g, i32 *size, i32 *parent) { size[v] = 1; for (i32 p = g->start[v]; p != -1; p = g->next[p]) { i32 u = g->v[p]; if (u == parent[v]) continue; parent[u] = v; dfs_size (u, g, size, parent); size[v] += size[u]; } } void rooted (i32 root, graph *g, i32 *size) { i32 *parent = ALLOC (g->n, i32); parent[root] = root; dfs_size (root, g, size, parent); init_graph (g); for (i32 i = 0; i < g->n; ++i) { if (i == root) continue; add_edge (g, parent[i], i); } free (parent); } void dfs_HL (i32 v, graph *g, i32 *size, i32 *index, i32 *id, i32 *path_parent) { static i32 k = 0; index[v] = k++; if (g->start[v] != -1) { i32 hv = g->v[g->start[v]]; for (i32 p = g->start[v]; p != -1; p = g->next[p]) { i32 u = g->v[p]; if (size[u] > size[hv]) hv = u; } id[hv] = id[v]; path_parent[hv] = path_parent[v]; dfs_HL (hv, g, size, index, id, path_parent); for (i32 p = g->start[v]; p != -1; p = g->next[p]) { i32 u = g->v[p]; if (u == hv) continue; id[u] = u; path_parent[u] = v; dfs_HL (u, g, size, index, id, path_parent); } } } typedef struct segment_tree { i32 *add; i32 *sum_c; i32 *sum_s; i32 size, bit; } segment_tree; segment_tree* new_segment_tree (i32 n, i32 *s, i32 *c, i32 *index) { i32 bit = 0; while ((1 << bit) < n) ++bit; segment_tree *seg = ALLOC (1, segment_tree); seg->add = ALLOC (2 << bit, i32); seg->sum_c = ALLOC (2 << bit, i32); seg->sum_s = ALLOC (2 << bit, i32); seg->size = 1 << bit; seg->bit = bit; for (i32 i = 0; i < n; ++i) { seg->sum_c[index[i] + seg->size] = c[i]; seg->sum_s[index[i] + seg->size] = s[i]; } for (i32 i = seg->size - 1; i > 0; --i) { seg->sum_c[i] = (seg->sum_c[2 * i] + seg->sum_c[2 * i + 1]) % mod; seg->sum_s[i] = (seg->sum_s[2 * i] + seg->sum_s[2 * i + 1]) % mod; } return seg; } i32 eval (segment_tree *s, i32 k) { return (s->sum_s[k] + (i64) s->add[k] * s->sum_c[k]) % mod; } void propagate (segment_tree *s, i32 x) { x += s->size; for (i32 i = s->bit; i > 0; --i) { i32 k = x >> i; s->add[2 * k] = (s->add[2 * k] + s->add[k]) % mod; s->add[2 * k + 1] = (s->add[2 * k + 1] + s->add[k]) % mod; s->add[k] = 0; s->sum_s[k] = (eval (s, 2 * k) + eval (s, 2 * k + 1)) % mod; } } void save (segment_tree *s, i32 x) { for (x = (x + s->size) >> 1; x > 0; x >>= 1) { s->sum_s[x] = (eval (s, 2 * x) + eval (s, 2 * x + 1)) % mod; } } void add (segment_tree *s, i32 l, i32 r, i32 v) { for (i32 x = l + s->size, y = r + s->size; x < y; x >>= 1, y >>= 1) { if (x & 1) { s->add[x] = (s->add[x] + v) % mod; x++; } if (y & 1) { --y; s->add[y] = (s->add[y] + v) % mod; } } save (s, l); save (s, r - 1); } i32 get_sum (segment_tree *s, i32 l, i32 r) { propagate (s, l); propagate (s, r - 1); i64 ans = 0; for (l += s->size, r += s->size; l < r; l >>= 1, r >>= 1) { if (l & 1) ans += eval (s, l++); if (r & 1) ans += eval (s, --r); } return ans % mod; } void run (void) { i32 n; scanf ("%" SCNi32, &n); i32 *s = ALLOC (2 * n, i32); i32 *c = s + n; for (i32 i = 0; i < 2 * n; ++i) { scanf ("%" SCNi32, s + i); } graph *g = new_graph (n, 2 * n); for (i32 i = 1; i < n; ++i) { i32 a, b; scanf ("%" SCNi32 "%" SCNi32, &a, &b); a--; b--; add_edge (g, a, b); add_edge (g, b, a); } i32 *size = ALLOC (n, i32); const i32 root = 0; rooted (root, g, size); i32 *index = ALLOC (n, i32); i32 *id = ALLOC (n, i32); i32 *path_parent = ALLOC (n, i32); id[root] = root; path_parent[root] = root; dfs_HL (root, g, size, index, id, path_parent); segment_tree *seg = new_segment_tree (n, s, c, index); i32 q; scanf ("%" SCNi32, &q); while (q--) { i32 op, x, y; scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &op, &x, &y); x--; y--; if (op == 0) { i32 z; scanf ("%" SCNi32, &z); while (id[x] != id[y]) { i32 rx = id[x]; i32 ry = id[y]; if (index[rx] > index[ry]) { add (seg, index[rx], index[x] + 1, z); x = path_parent[x]; } else { add (seg, index[ry], index[y] + 1, z); y = path_parent[y]; } } add (seg, MIN (index[x], index[y]), MAX (index[x], index[y]) + 1, z); } else { i64 ans = 0; while (id[x] != id[y]) { i32 rx = id[x]; i32 ry = id[y]; if (index[rx] > index[ry]) { ans += get_sum (seg, index[rx], index[x] + 1); x = path_parent[x]; } else { ans += get_sum (seg, index[ry], index[y] + 1); y = path_parent[y]; } } ans += get_sum (seg, MIN (index[x], index[y]), MAX (index[x], index[y]) + 1); ans %= mod; printf ("%" PRIi64 "\n", ans); } } } int main (void) { run(); return 0; }