#define NDEBUG #include #include #include #include #include template class link_cut_tree { public: using value_structure = ValueMonoid; using value_type = typename value_structure::value_type; using operator_structure = OperatorMonoid; using operator_type = typename operator_structure::value_type; using modifier_type = Modifier; using size_type = ::std::size_t; private: class node_type { public: node_type *left, *right, *parent; typename link_cut_tree::value_type value, sum; typename link_cut_tree::operator_type lazy; bool reversed; // reverse->lazy node_type(value_type &&v, operator_type &&o) : value(::std::move(v)), sum(value), lazy(::std::move(o)), reversed(0) { } }; using pointer = node_type *; using const_pointer = const node_type *; ::std::vector nodes; size_type size_; value_structure vf; operator_structure of; modifier_type mf; pointer nil() noexcept { return nodes.data(); } void reverse(const pointer ptr) { ptr->lazy = of.reverse(ptr->lazy); ptr->reversed ^= 1; } void push(const pointer ptr) { if (ptr->reversed) { ptr->reversed = 0; ptr->value = vf.reverse(ptr->value); ::std::swap(ptr->left, ptr->right); reverse(ptr->left); reverse(ptr->right); } ptr->left->lazy = of(ptr->left->lazy, ptr->lazy); ptr->right->lazy = of(ptr->right->lazy, ptr->lazy); ptr->value = mf(ptr->value, ptr->lazy); ptr->lazy = of.identity(); } void propagate(pointer ptr) { pointer prev = nullptr; while (ptr != nil()) { ::std::swap(ptr->parent, prev); ::std::swap(ptr, prev); } while (prev) { push(prev); ::std::swap(prev->parent, ptr); ::std::swap(prev, ptr); } nil()->sum = vf.identity(); nil()->lazy = of.identity(); nil()->reversed = 0; } value_type reflect(const const_pointer ptr) { return mf(ptr->reversed ? vf.reverse(ptr->sum) : ptr->sum, ptr->lazy); } void calc(const pointer ptr) { ptr->sum = vf(vf(reflect(ptr->left), ptr->value), reflect(ptr->right)); } static void set_l(const pointer ptr, const pointer ch) { ptr->left = ch; ch->parent = ptr; } static void set_r(const pointer ptr, const pointer ch) { ptr->right = ch; ch->parent = ptr; } void rotate_l(const pointer ptr, const pointer ch) { set_r(ptr, ch->left); calc(ptr); set_l(ch, ptr); } void rotate_r(const pointer ptr, const pointer ch) { set_l(ptr, ch->right); calc(ptr); set_r(ch, ptr); } void splay(const pointer ptr) { for (pointer x, y = ptr;;) { x = ptr->parent; if (x->left == y) { y = x->parent; ptr->parent = y->parent; if (y->left == x) rotate_r(y, x), rotate_r(x, ptr); else if (y->right == x) rotate_l(y, ptr), rotate_r(x, ptr); else return ptr->parent=y,rotate_r(x, ptr); } else if (x->right == y) { y = x->parent; ptr->parent = y->parent; if (y->right == x) rotate_l(y, x), rotate_l(x, ptr); else if (y->left == x) rotate_r(y, ptr), rotate_l(x, ptr); else return ptr->parent = y, rotate_l(x, ptr); } else { return; } } } void expose(const pointer ptr) { propagate(ptr); pointer x = ptr, prev = nil(); while (x != nil()) { splay(x); x->right = prev; calc(x); prev = x; x = x->parent; } splay(ptr); calc(ptr); } void reroot(const pointer ptr) { expose(ptr); reverse(ptr); } pointer get_ptr(const size_type i) noexcept { return nodes.data() + 1 + i; } public: link_cut_tree() : link_cut_tree(0) {} explicit link_cut_tree(const size_type size, const value_structure &x = value_structure(), const operator_structure &y = operator_structure(), const modifier_type &z = modifier_type()) : size_(size), vf(x), of(y), mf(z) { nodes.reserve(size_ + 1); nodes.emplace_back(vf.identity(), of.identity()); const pointer n = nil(); n->left = n->right = n->parent = n; nodes.resize(size_ + 1, nodes.front()); } bool empty() const noexcept { return !size_; } size_type size() const noexcept { return size_; } bool connected(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); expose(get_ptr(v)); expose(get_ptr(u)); return nodes[v + 1].parent != nil() || v == u; } value_type fold(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); return nodes[u + 1].sum; } void link(const size_type parent, const size_type child) { assert(parent < size()); assert(child < size()); assert(!connected(parent, child)); reroot(get_ptr(child)); nodes[child + 1].parent = get_ptr(parent); } void cut(const size_type v) { assert(v < size()); expose(get_ptr(v)); nodes[v + 1].left->parent = nil(); nodes[v + 1].left = nil(); nodes[v + 1].sum = nodes[v + 1].value; } void update(const size_type v, const size_type u, const operator_type &data) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); nodes[u + 1].lazy = data; } template void update(const size_type v, const F &f) { assert(v < size()); expose(get_ptr(v)); nodes[v + 1].value = f(nodes[v + 1].value); calc(get_ptr(v)); } }; #include template struct modint { private: using uint32 = std::uint_fast32_t; using uint64 = std::uint_fast64_t; public: uint32 a; modint() :a(0) {} modint(const std::int_fast64_t &x) :a(set(x%MODULO + MODULO)) {} static uint32 set(const uint32 &x) { return(x (const modint &o)const { return a > o.a; } bool operator>=(const modint &o)const { return a >= o.a; } explicit operator bool()const { return a; } explicit operator uint32()const { return a; } modint operator^(uint32 x)const { uint64 t = a, u = 1; while (x) { if (x & 1) u = u*t%MODULO;t = (t*t) % MODULO;x >>= 1; } return make(u); } }; using mint = modint<1000000007>; struct city{ using value_type = std::pair; using cref = const value_type &; value_type operator()(cref x, cref y)const { return { x.first + y.first,x.second + y.second }; } value_type identity()const { return { 0,0 }; } value_type reverse(cref x)const { return x; } }; struct parade { using value_type = mint; mint operator()(mint x, mint y)const { return x + y; } mint identity()const { return 0; } mint reverse(mint x)const { return x; } }; struct act { std::pair operator()(const std::pair &x, mint y)const { return { x.first + x.second*y,x.second }; } }; #include int main() { using P = std::pair; int n; scanf("%d", &n); link_cut_tree T(n); std::vector s(n), c(n); for (auto &e : s) scanf("%u", &e.a); for (auto &e : c) scanf("%u", &e.a); for (int i = 0;i < n;++i) T.update(i, [&](const P&x) {return P(s[i], c[i]);}); while(--n) { int a, b; scanf("%d%d", &a, &b); --a;--b; T.link(a, b); } int q; scanf("%d", &q); while(q--) { int t, x, y; mint z; scanf("%d%d%d", &t, &x, &y); --x;--y; if (t) { printf("%u\n", T.fold(x, y).first.a); } else { scanf("%u", &z.a); T.update(x, y, mint(z)); } } return 0; }