#define NDEBUG #define _CRT_SECURE_NO_WARNINGS #include #include #include #include template class LinkCutTree { public: using value_type = ValueMonoid; using reference = value_type &; using const_reference = const value_type &; 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(); return t->reversed ? m(~t->sum, t->lazy) : 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) { (x->left == pp ? x->left : 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; } recalc(t); } 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); } using container_type = std::vector; public: using size_type = typename container_type::size_type; private: container_type tree; const Modify m; void expose(node_t *const n) { propagate(n); expose(n, nullptr); splay(n); } 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); 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(); } /* struct vis { int l, r, p, rev; }; std::vector v; int ch(node_t *n) { if (n == nil() || !n) return -9; return n - &tree[0]; } void scan(void) { v = std::vector(size()); for (int i = 0; i < size(); ++i) { v[i] = { ch(tree[i].left), ch(tree[i].right), ch(tree[i].par), tree[i].reversed }; } } //*/ }; #include template struct modint { using uint32 = std::uint_fast32_t; using uint64 = std::uint_fast64_t; uint32 a; modint() :a(0) {} modint(std::int_fast64_t x) :a(norms(x%MOD + MOD)) {} static uint32 norms(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 = (uint64)a;uint64 u = 1; while (x) { if (x & 1) u = u*t%MOD;t = (t*t) % MOD;x >>= 1; } return make((uint32)u); } /* friend std::istream &operator>>(std::istream &is, modint &o) { std::int_fast64_t x;is >> x;o = modint(x);return(is); } friend std::ostream &operator<<(std::ostream &os, const modint &o) { return os << o.a; } */ }; using mint = modint<1000000007>; struct p { mint z; p(mint x = 0) :z(x) {} p operator+(const p &o)const { return p(z + o.z); } }; struct m { mint s, c; m(mint x = 0, mint y = 0) :s(x), c(y) {} m operator~()const { return *this; } m operator+(const m &o)const { return m(s + o.s, c + o.c); } m operator*(const p &o)const { return m(s + c*o.z, c); } }; struct hoge { m operator()(const m &x, const p &y)const { return x*y; } }; #include #include int main(void) { int n; scanf("%d", &n); std::vector d(n); for (auto &e : d)scanf("%u", &e.s.a); for (auto &e : d)scanf("%u", &e.c.a); LinkCutTree T(d); int a, b, c; while (--n) { scanf("%d %d", &a, &b); T.link(a - 1, b - 1); } scanf("%d", &n); mint z; while (n--) { scanf("%d %d %d", &c, &a, &b); if (c) { printf("%u\n", T.path(a - 1, b - 1).s.a); } else { scanf("%u", &z.a); T.update(a - 1, b - 1, p(z)); } } return 0; }