#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using int32 = std::int_fast32_t; using int64 = std::int_fast64_t; using uint32 = std::uint_fast32_t; using uint64 = std::uint_fast64_t; using intl32 = std::int_least32_t; using intl64 = std::int_least64_t; using uintl32 = std::uint_least32_t; using uintl64 = std::uint_least64_t; #include #include #include using int32 = std::int_fast32_t; using int64 = std::int_fast64_t; using uint32 = std::uint_fast32_t; using uint64 = std::uint_fast64_t; using intl32 = std::int_least32_t; using intl64 = std::int_least64_t; using uintl32 = std::uint_least32_t; using uintl64 = std::uint_least64_t; template class LC { struct node { node *left, *right, *per; Mo data, sum; Op lazy; bool isroot, rev; static node *const nil; void push() { if (rev) { left->rev ^= 1; right->rev ^= 1; std::swap(left, right); data = ~data; rev = 0; } data = data * lazy; left->lazy = left->lazy * lazy; right->lazy = right->lazy * lazy; lazy = Op(); } Mo reflect() const { return rev ? ~sum * lazy : sum * lazy; } void fix() { if (rev) sum = ~sum; sum = sum * lazy; push(); } void propagate() { if (per) per->propagate(); push(); } void haulL(node *const l) { left = l; l->per = this; } void haulR(node *const r) { right = r; r->per = this; } void splay() { node *x = this, *pp = per; left->fix(); right->fix(); nil->sum = Mo(); nil->lazy = Op(); nil->rev = 0; while (!x->isroot) { if (pp) { if (pp->left == x) pp->left = this; else pp->right = this; } if (per->isroot) { if (per->left == this) { per->left = right; per->sum = right->sum + per->data + per->right->reflect(); right = per; x = per; per = per->per; right->per = this; } else { per->right = left; per->sum = per->left->reflect() + per->data + left->sum; left = per; x = per; per = per->per; left->per = this; } break; } x = per->per; pp = x->per; if (per->left == this) { if (x->left == per) { x->haulL(per->right); x->sum = x->left->reflect() + x->data + x->right->reflect(); per->haulR(x); per->haulL(right); per->sum = right->sum + per->data + x->sum; haulR(per); } else { x->haulR(left); x->sum = x->left->reflect() + x->data + left->sum; per->haulL(right); per->sum = right->sum + per->data + per->right->reflect(); haulL(x); haulR(per); } } else { if (x->right == per) { x->haulL(per->left); x->sum = x->left->reflect() + x->data + x->right->reflect(); per->haulL(x); per->haulR(left); per->sum = x->sum + per->data + left->sum; haulL(per); } else { x->haulL(right); x->sum = right->sum + x->data + x->right->reflect(); per->haulR(left); per->sum = per->left->reflect() + per->data + left->sum; haulR(x); haulL(per); } } per = pp; } sum = left->sum + data + right->sum; x->isroot = 0; } void expose(node *const prev) { splay(); if (right != nil) right->isroot = 1; right = prev; sum = left->sum + data + right->sum; if (per) per->expose(this); else isroot = 1; } }; std::vector tree; void expose(node *const n) { n->propagate(); n->expose(node::nil); n->splay(); n->isroot = 1; ; n->sum = n->left->sum + n->data + n->right->sum; } public: LC(const uint32 size) : tree(size, { node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0 }) {} LC(const std::vector &a) : tree(a.size(), { node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0 }) { for (uint32 i = 0; i < a.size(); ++i) tree[i].data = tree[i].sum = a[i]; } void link(uint32 child, uint32 per) { evert(child); tree[child].per = &tree[per]; } void cut(uint32 child) { node *n = &tree[child]; expose(n); n->left->per = nullptr; n->left->isroot = 1; n->left = node::nil; n->sum = n->data; } void update(uint32 u, uint32 v, const Op &data) { evert(u); expose(&tree[v]); tree[v].lazy = data; } Mo path(uint32 u, uint32 v) { evert(u); expose(&tree[v]); return tree[v].sum; } void evert(uint32 v) { expose(&tree[v]); tree[v].rev ^= 1; } }; template typename LC::node *const LC::node::nil = []() { LC::node *const ret = new LC::node; ret->left = ret->right = nil; ret->data = ret->sum = Mo(); return ret; }(); static constexpr uint64 MOD = 1000000007; struct p { uint64 data; bool has; p():has(1) {} p(uint64 x) :data(x),has(0) {} p operator*(const p &other) { if (other.has) return *this; if (has) return other; return p((data + other.data) % MOD); } }; struct meguru { uint64 s, c; meguru():s(0),c(0) {} meguru(uint64 x, uint64 y) :s(x), c(y) {} meguru operator~()const { return *this; } meguru operator+(const meguru &other)const { return meguru((s + other.s) % MOD, (c + other.c) % MOD); } meguru operator*(const p &other)const { if (other.has) return *this; return meguru((s + c*other.data) % MOD, c); } }; int main(void) { std::ios::sync_with_stdio(false); std::cin.tie(0); uint32 n; std::cin >> n; std::vector D(n); uint64 s, c; for (uint32 i = 0;i < n;++i) { std::cin >> s; D[i].s = s; } for (uint32 i = 0;i < n;++i) { std::cin >> c; D[i].c = c; } LC L(D); uint32 a, b; for (uint32 i = 1;i < n;++i) { std::cin >> a >> b; L.link(a - 1, b - 1); //L.scan(); } uint32 q; std::cin >> q; uint64 que, x, y, z; while (q--) { //L.scan(); std::cin >> que >> x >> y; if (que) { std::cout << L.path(x - 1, y - 1).s << "\n"; } else { std::cin >> z; L.update(x - 1, y - 1, p(z)); } } return 0; }