#include #define rep(i, a) for (int i = 0; i < (a); i++) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) for (int i = (a) - 1; i >= 0; i--) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; const int inf = 1e9; const ll mod = 1e9 + 7; template struct RMQ { vector seg; int size; T inf; RMQ(int n, T inf) { this->inf = inf; size = 1; while (size < n) size *= 2; seg.resize(size * 2 - 1, inf); } void update(int k, T x) { k += size - 1; seg[k] = x; while (k > 0) { k = (k - 1) / 2; seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return inf; if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; struct LCA { RMQ> rmq; vector > euler; vector > G; vector id; int root; LCA(int V) : rmq(V * 2 - 1, make_pair(inf, inf)), G(V), id(V), euler(V * 2 - 1) {} void add(int u, int v) { G[u].push_back(v); G[v].push_back(u); } void dfs(int curr, int prev, int depth, int &k) { id[curr] = k; euler[k++] = make_pair(depth, curr); for (int next : G[curr]) if (next != prev) { dfs(next, curr, depth + 1, k); euler[k++] = make_pair(depth, curr); } } void build(int root = 0) { this->root = root; int k = 0; dfs(root, -1, 0, k); rep (i, euler.size()) { rmq.update(i, euler[i]); } } int query(int u, int v) { return rmq.query(min(id[u], id[v]), max(id[u], id[v]) + 1).second; } }; struct HL { vector> G, color; vector parent, head, order, size, heads; int root; map> path; HL(int n) : G(n), color(n), parent(n), head(n), order(n), size(n) {} void add(int u, int v) { G[u].push_back(v); G[v].push_back(u); } int dfs(int curr, int prev) { int res = 1; parent[curr] = prev; rep (i, G[curr].size()) { int next = G[curr][i]; if (next == prev) continue; int d = dfs(next, curr); color[curr][i] = d; res += d; } int maxi = max_element(color[curr].begin(), color[curr].end()) - color[curr].begin(); rep (i, G[curr].size()) { color[curr][i] = maxi == i; } return res; } void dfs2(int curr, int prev) { rep (i, G[curr].size()) { int next = G[curr][i]; if (next == prev) continue; if (color[curr][i]) { head[next] = head[curr]; order[next] = order[curr] + 1; } dfs2(next, curr); } } void build(int root = 0) { this->root = root; int V = G.size(); rep (i, V) color[i].resize(G[i].size()); dfs(root, -1); rep (i, V) head[i] = i; dfs2(root, -1); rep (i, V) size[head[i]]++; rep (i, V) { if (i == head[i]) { heads.push_back(i); path[i].resize(size[i]); } } rep (i, V) { path[head[i]][order[i]] = i; } } int skip(int v) { return parent[head[v]]; } int vid(int h, int ord) { return path[h][ord]; } }; struct HLIterator { int u, v, l; HL *hl; LCA *lca; HLIterator(HL *hl, int u) : hl(hl), u(u), v(0), l(hl->root) {} HLIterator(HL *hl, LCA *lca, int u, int v) : hl(hl), lca(lca), u(u), v(v) { l = lca->query(u, v); } // head, [from, to) tuple next() { if (hl->head[l] != hl->head[u]) { int pu = u; u = hl->skip(u); return make_tuple(hl->head[pu], 0, hl->order[pu] + 1); } if (hl->head[l] != hl->head[v]) { int pv = v; v = hl->skip(v); return make_tuple(hl->head[pv], 0, hl->order[pv] + 1); } int a = min(hl->order[u], hl->order[v]); int b = max(hl->order[u], hl->order[v]); u = -1; v = -1; return make_tuple(hl->head[l], a, b + 1); } bool has_next() { return u != -1 && v != -1; } }; ll modulo(ll a) { a %= mod; a += mod; a %= mod; return a; } struct SegmentTree { vector seg, lazy, weight, wsum; int size; void init(int n) { size = 1; while (size < n) size *= 2; seg.resize(size * 2); lazy.resize(size * 2); weight.resize(size); } void set_value(int k, ll v) { seg[k + size - 1] = v; } void set_weight(int k, ll w) { weight[k] = w; } void build() { wsum.resize(size + 1); rep (i, size) { wsum[i + 1] += wsum[i] + weight[i]; wsum[i + 1] %= mod; } repr (i, size - 1) { seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2]; seg[i] %= mod; } } void evallazy(int k, int l, int r) { seg[k] += lazy[k] * (wsum[r] - wsum[l]); seg[k] = modulo(seg[k]); if (r - l > 1) { (lazy[k * 2 + 1] += lazy[k]) %= mod; (lazy[k * 2 + 2] += lazy[k]) %= mod; } lazy[k] = 0; } void update(int a, int b, ll v, int k, int l, int r) { evallazy(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = v; evallazy(k, l, r); } else { update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; seg[k] %= mod; } } void update(int a, int b, ll v) { update(a, b, v, 0, 0, size); } ll query(int a, int b, int k, int l, int r) { evallazy(k, l, r); if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; ll res = 0; res += query(a, b, k * 2 + 1, l, (l + r) / 2); res += query(a, b, k * 2 + 2, (l + r) / 2, r); return res % mod; } ll query(int a, int b) { return query(a, b, 0, 0, size); } }; map seg; void update(HL &hl, LCA &lca, int x, int y, int z) { HLIterator it(&hl, &lca, x, y); while (it.has_next()) { auto t = it.next(); int head = get<0>(t); int l = get<1>(t); int r = get<2>(t); seg[head].update(l, r, z); } } int query(HL &hl, LCA &lca, int x, int y) { HLIterator it(&hl, &lca, x, y); ll res = 0; while (it.has_next()) { auto t = it.next(); int head = get<0>(t); int l = get<1>(t); int r = get<2>(t); res += seg[head].query(l, r); res %= mod; } return res; } struct Stopwatch { double begin; Stopwatch() { start(); } void start() { begin = clock(); } double elapsed() { double end = clock(); double res = (double)(end - begin) / CLOCKS_PER_SEC * 1000.0; begin = end; return res; } void display(string text) { // cerr << text << ":" << elapsed() << "ms" << endl; } }; int main() { Stopwatch whole; int N; cin >> N; vector S(N), C(N); rep (i, N) scanf("%d", &S[i]); rep (i, N) scanf("%d", &C[i]); HL hl(N); LCA lca(N); rep (i, N - 1) { int a, b; cin >> a >> b; a--; b--; hl.add(a, b); lca.add(a, b); } Stopwatch sw; hl.build(); sw.display("build HL"); lca.build(); sw.display("build LCA"); for (int h : hl.heads) { seg[h].init(hl.size[h]); } sw.display("init SegmentTree"); rep (i, N) { seg[hl.head[i]].set_value(hl.order[i], S[i]); seg[hl.head[i]].set_weight(hl.order[i], C[i]); } for (int h : hl.heads) { seg[h].build(); } sw.display("build SegmentTree"); int Q; cin >> Q; while (Q--) { int q; scanf("%d", &q); if (q == 0) { int x, y, z; scanf("%d%d%d", &x, &y, &z); x--; y--; update(hl, lca, x, y, z); } else { int x, y; scanf("%d%d", &x, &y); x--; y--; ll ans = query(hl, lca, x, y); printf("%d\n", (int)ans); } } sw.display("query"); whole.display("whole"); }