//#define NDEBUG #define _CRT_SECURE_NO_WARNINGS #include #include #include template class LinkCutTree { public: using value_type = ValueMonoid; using operator_type = OperatorMonoid; private: struct node_t { node_t *left, *right, *par; value_type value, sum; operator_type lazy; bool isroot, reversed; node_t() : left(nullptr), right(nullptr), par(nullptr), value(), sum(), lazy(), isroot(1), reversed(0) {} bool isleft() const { return par->left == this; } void assign(const operator_type &data) { lazy = lazy + data; } void haulL(node_t *const t) { left = t; if (t) t->par = this; } void haulR(node_t *const t) { right = t; if (t) t->par = this; } }; value_type reflect(const node_t *const t) const { if (!t) return value_type(); if (t->reversed) return m(~t->sum, t->lazy); return m(t->sum, t->lazy); } void recalc(node_t *const t) { t->sum = reflect(t->left) + t->value + reflect(t->right); } void splay(node_t *const t) { node_t *p, *pp = t, *x = t->par; while (!t->isroot) { if (x->left == pp) x->left = t; else x->right = t; p = t->par; if (p->isroot) { t->par = p->par; std::swap(t->isroot, p->isroot); if (p->left == t) p->haulL(t->right), t->haulR(p); else p->haulR(t->left), t->haulL(p); recalc(p); break; } pp = p->par; x = pp->par; std::swap(t->isroot, pp->isroot); if (t->isleft()) { if (p->isleft()) pp->haulL(p->right), p->haulR(pp); else pp->haulR(t->left), t->haulL(pp); p->haulL(t->right); t->haulR(p); } else { if (p->isleft()) pp->haulL(t->right), t->haulR(pp); else pp->haulR(p->left), p->haulL(pp); p->haulR(t->left); t->haulL(p); } recalc(pp); recalc(p); t->par = x; } } void expose(node_t *const t, node_t *const prev) { splay(t); if (t->right) t->right->isroot = 1; t->right = prev; if (prev) prev->isroot = 0; recalc(t); if (t->par) expose(t->par, t); } void push(node_t *const t) { if (t->left) t->left->assign(t->lazy); if (t->right) t->right->assign(t->lazy); t->value = m(t->value, t->lazy); t->lazy = operator_type(); if (!t->reversed) return; std::swap(t->left, t->right); if (t->left) t->left->reversed ^= 1; if (t->right) t->right->reversed ^= 1; t->value = ~t->value; t->reversed = 0; } void propagate(node_t *const t) { if (t->par) propagate(t->par); push(t); } void expose(node_t *const n) { propagate(n); expose(n, nullptr); splay(n); recalc(n); } using container_type = std::vector; public: using size_type = typename container_type::size_type; private: container_type tree; const Modify m; public: explicit LinkCutTree(const size_type size, const Modify &m = Modify()) : tree(size), m(m) {} explicit LinkCutTree(const std::vector &a, const Modify &m = Modify()) : tree(a.size()), m(m) { for (size_type i = 0; i < a.size(); ++i) tree[i].value = tree[i].sum = a[i]; } void link(const size_type child, const size_type parent) { assert(child < size()); assert(parent < size()); reroot(child); tree[child].par = &tree[parent]; } void cut(const size_type child) { assert(child < size()); node_t *const n = &tree[child]; expose(n); if (n->left) n->left->isroot = 1, n->left->par = nullptr; n->left = nullptr; n->sum = n->value; } void update(const size_type u, const size_type v, const operator_type &data) { assert(u < size()); assert(v < size()); reroot(u); expose(&tree[v]); tree[v].assign(data); } value_type path(const size_type u, const size_type v) { assert(u < size()); assert(v < size()); reroot(u); expose(&tree[v]); return reflect(&tree[v]); } void reroot(const size_type v) { assert(v < size()); expose(&tree[v]); tree[v].reversed ^= 1; } size_type size() const noexcept { return tree.size(); } bool empty() const noexcept { return tree.empty(); } }; #include using uint32 = std::uint_fast32_t; constexpr uint32 MOD = 1000000007; struct parade { uint32 z; parade(uint32 z = 0) :z(z) {} parade operator+(const parade &o)const { return parade((z + o.z) % MOD); } }; struct city { uint32 s, c; city(uint32 s = 0, uint32 c = 0) :s(s), c(c) {} city operator~()const { return *this; } city operator+(const city &o)const { return city((s + o.s) % MOD, (c + o.c) % MOD); } }; struct hoge { city operator()(const city &x, const parade &y)const { return city((static_cast(x.c)*y.z + x.s) % MOD, x.c); } }; #include #include int main(void) { int n; scanf("%d", &n); std::vector d(n); for (auto &e : d)scanf("%u", &e.s); for (auto &e : d)scanf("%u", &e.c); LinkCutTree T(d); while (--n) { int a, b; scanf("%d %d", &a, &b); T.link(a - 1, b - 1); } int q; scanf("%d", &q); while (q--) { int t, x, y; parade z; scanf("%d %d %d", &t, &x, &y); --x, --y; if (t) { printf("%u\n", T.path(x, y).s); } else { scanf("%u", &z.z); T.update(x, y, z); } } return 0; }