//#define NDEBUG #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include static constexpr double PI = 3.1415926535897932; 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; void yes(bool c) { puts(c ? "yes" : "no"); } void Yes(bool c) { puts(c ? "Yes" : "No"); } void YES(bool c) { puts(c ? "YES" : "NO"); } void pos(bool c) { puts(c ? "possible" : "impossible"); } void Pos(bool c) { puts(c ? "Possible" : "Impossible"); } void POS(bool c) { puts(c ? "POSSIBLE" : "IMPOSSIBLE"); } templatebool bmaxi(T&a, const T&b) { if (bbool bmini(T&a, const T&b) { if (abool nmaxi(T&a, const T&b) { if (abool nmini(T&a, const T&b) { if (bauto scan(T&d)->typename std::enable_if::value>::type { d.clear();int c = fgetc(stdin);while (c<'a' || 'z'auto scan(T&d)-> typename std::enable_if::value>::type { scanf("%lf", &d); } template auto scan(T&d)->typename std::enable_if::value == std::is_same::value>::type { d = 0;int c = fgetc(stdin); while (c<'0' || '9'auto scan(T&d)->typename std::enable_if::value != std::is_same::value>::type { d = 0;int c = fgetc(stdin);bool f = 0;while (c<'0' || '9'void scan(F&f, R&...r) { scan(f);scan(r...); } #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 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, *per; value_type value, sum; operator_type lazy; bool isroot, reversed; static node_t *const nil; node_t() : left(nil), right(nil), per(nullptr), value(value_type()), sum(value_type()), lazy(operator_type()), isroot(1), reversed(0) {} bool isleft() const { return per->left == this; } value_type reflect() { return reversed ? ~(sum * lazy) : (sum * lazy); } void assign(const operator_type &data) { lazy = lazy * data; } void recalc() { sum = left->reflect() + value + right->reflect(); } void haulL(node_t *const t) { left = t, t->per = this; } void haulR(node_t *const t) { right = t, t->per = this; } void set(node_t *const ch) { if (isroot) ch->per = per; else isleft() ? per->haulL(ch) : per->haulR(ch); std::swap(isroot, ch->isroot); } void rotateL() { node_t *const t = per; t->set(this); t->haulR(left); haulL(t); t->recalc(); } void rotateR() { node_t *const t = left; t->set(this); t->haulL(right); haulR(t); t->recalc(); } void push() { left->assign(lazy); right->assign(lazy); lazy = operator_type(); if (!reversed) return; std::swap(left, right); left->reversed ^= 1; right->reversed ^= 1; value = ~value; reversed = 0; } void propagate() { if (per) per->propagate(); push(); } void splay() { while (!isroot) { if (per->isroot) { isleft() ? rotateR() : rotateL(); break; } if (isleft()) { if (per->isleft()) per->rotateR(), rotateR(); else rotateR(), rotateL(); } else { if (per->isleft()) rotateL(), rotateR(); else per->rotateL(), rotateL(); } } recalc(); } void expose(node_t *const prev) { splay(); right->isroot = 1; right = prev; prev->isroot = 0; recalc(); if (per) per->expose(this); } }; public: using size_type = typename std::vector::size_type; private: std::vector tree; void expose(node_t *const n) { n->propagate(); n->expose(node_t::nil); n->splay(); n->recalc(); } /* struct vis { int32 l, r, p, rev; }; std::vector v; */ public: LinkCutTree(const size_type size) : tree(size) {} LinkCutTree(const std::vector &a) : tree(a.size()) { for (uint32 i = 0; i < a.size(); ++i) { tree[i].value = tree[i].sum = a[i]; } } void link(const size_type child, const size_type per) { evert(child); tree[child].per = &tree[per]; } void cut(const size_type child) { node_t *const n = &tree[child]; expose(n); n->left->per = nullptr; n->left->isroot = 1; n->left = node_t::nil; n->sum = n->value; } void update(const size_type u, const size_type v, const operator_type &data) { evert(u); expose(&tree[v]); tree[v].assign(data); } value_type path(const size_type u, const size_type v) { evert(u); expose(&tree[v]); return tree[v].reflect(); } void evert(const size_type v) { expose(&tree[v]); tree[v].reversed ^= 1; } /* int32 ch(node_t *n) { if (!n) return -9; return n - &tree[0]; } void scan(void) { v = std::vector(tree.size()); for (uint32 i = 0;i < tree.size();++i) { v[i] = { ch(tree[i].left),ch(tree[i].right),ch(tree[i].per),tree[i].b & 2 }; } } */ }; template typename LinkCutTree::node_t *const LinkCutTree::node_t::nil = []() { const auto ret = new LinkCutTree::node_t; ret->left = ret->right = ret; ret->per = nullptr; ret->value = ret->sum = value_type(); ret->lazy = operator_type(); ret->isroot = 0; ret->reversed = 0; return ret; }(); #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); } }; int main(void) { uint32 n; scan(n); std::vector d(n); for (uint32 i = 0;i < n;++i) scan(d[i].s.a); for (uint32 i = 0;i < n;++i) scan(d[i].c.a); LinkCutTree T(d); uint32 a, b,c; while(--n){ scan(a, b); T.link(a-1, b-1); } scan(n); mint z; while (n--) { scan(c, a, b); if (c) { printf("%u\n", T.path(a - 1, b - 1).s.a); } else { scan(z.a); T.update(a - 1, b - 1, p(z)); } } return 0; }