//#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; 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->haulL(right); per->sum = right->sum + per->data + per->right->reflect(); right = per; x = per; per = per->per; right->per = this; } else { per->haulR(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->haulR(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 = ret; ret->data = ret->sum = Mo(); 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); LC 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; }