#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<auto&operator<<(ostream&o,pairp){return o<<"{"<auto&operator<<(ostream&o,sets){for(auto&e:s)o< auto&operator<<(ostream&o,priority_queueq){while(!q.empty())o<auto&operator<<(ostream&o,mapm){for(auto&e:m)o<auto&operator<<(ostream&o,vectorv){for(auto&e:v)o<void ashow(T t,A...a){cout< P; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector

vp; typedef vector vd; typedef vector vs; const int MAX_N = 200005; template class BSTNode { public: int from, to, sz; _Tp value, al, lazy; BSTNode *left, *right, *par; BSTNode(const int _from, const int _to) noexcept : from(_from), to(_to), sz(0), value(id1), al(id2), lazy(id1), left(nullptr), right(nullptr), par(nullptr){} BSTNode(const int _from, const int _to, const int _sz, const _Tp& _value) noexcept : from(_from), to(_to), sz(_sz), value(_value), al(id2), lazy(id1), left(nullptr), right(nullptr), par(nullptr){} static const _Tp id1 = (_Tp)0; static const _Tp id2 = (_Tp)0; static void opr1(_Tp& arg1, const _Tp arg2){ arg1 += arg2; } static _Tp opr2(const _Tp arg1, const _Tp arg2){ return arg1 + arg2; } inline bool IsRoot() const { return !par; } inline bool IsVertex() const noexcept { return from == to; } void push() noexcept { if(lazy != id1){ if(IsVertex()) opr1(value, lazy); al += lazy * sz; if(left) opr1(left->lazy, lazy); if(right) opr1(right->lazy, lazy); lazy = id1; } } void eval() noexcept { sz = IsVertex(), al = value; if(left) left->push(), sz += left->sz, al = opr2(left->al, al); if(right) right->push(), sz += right->sz, al = opr2(al, right->al); } void rotate(const bool right_) noexcept { BSTNode *p = par, *g = p->par; if(right_){ if((p->left = right)) right->par = p; right = p, p->par = this; }else{ if((p->right = left)) left->par = p; left = p, p->par = this; } p->eval(), eval(); if(!(par = g)) return; if(g->left == p) g->left = this; if(g->right == p) g->right = this; g->eval(); } }; template BSTNode<_Tp>* splay(BSTNode<_Tp> *u) noexcept { if(!u) return nullptr; while(!(u->IsRoot())){ BSTNode<_Tp> *p = u->par, *gp = p->par; if(p->IsRoot()){ // zig p->push(), u->push(); u->rotate((u == p->left)); }else{ gp->push(), p->push(), u->push(); bool flag = (u == p->left); if((u == p->left) == (p == gp->left)){ // zig-zig p->rotate(flag), u->rotate(flag); }else{ // zig-zag u->rotate(flag), u->rotate(!flag); } } } u->push(); return u; } template BSTNode<_Tp>* join(BSTNode<_Tp> *root1, BSTNode<_Tp> *root2) noexcept { if(!root1 || !root2) return root1 ? root1 : root2; BSTNode<_Tp> *cur = nullptr, *nx = root1; do{ cur = nx, cur->push(), nx = cur->right; }while(nx); BSTNode<_Tp> *ver = splay(cur); ver->right = root2, ver->eval(), root2->par = ver; return ver; } template pair*, BSTNode<_Tp>*> split_lower_bond(BSTNode<_Tp> *ver) noexcept { BSTNode<_Tp> *res = splay(ver)->left; ver->left = nullptr, ver->eval(); if(res) res->par = nullptr; return make_pair(res, ver); } template pair*, BSTNode<_Tp>*> split_upper_bond(BSTNode<_Tp> *ver) noexcept { BSTNode<_Tp> *res = splay(ver)->right; ver->right = nullptr, ver->eval(); if(res) res->par = nullptr; return make_pair(ver, res); } template class EulerTourTree { private: struct edge { int from, to; edge(){} edge(int _from, int _to) : from(_from), to(_to){} bool operator<(const edge& val) const noexcept { return (from == val.from) ? (to < val.to) : (from < val.from); } }; void reroot(BSTNode *ver) noexcept { BSTNode *res = splay(ver)->left; if(!res) return; while(ver->right) ver->push(), ver = ver->right; ver->right = res, ver->eval(), res->par = ver, splay(res); } void link(BSTNode *ver1, BSTNode *ver2) noexcept { reroot(ver1), reroot(ver2); BSTNode* e1 = new BSTNode(ver1->from, ver2->from); BSTNode* e2 = new BSTNode(ver2->from, ver1->from); edge_set[(edge){ver1->from, ver2->from}] = e1; edge_set[(edge){ver2->from, ver1->from}] = e2; join(join(ver1, e1), join(ver2, e2)); } void cut(BSTNode *edge1, BSTNode *edge2) noexcept { splay(edge1), splay(edge2); BSTNode *p = edge1->par; bool _right = (edge1 == edge2->right); if(p != edge2){ _right = (p == edge2->right); p->par = nullptr, edge1->rotate((edge1 == p->left)); } if(edge1->left) edge1->left->par = nullptr; if(edge1->right) edge1->right->par = nullptr; if(_right){ if(edge2->left) edge2->left->par = nullptr; join(edge2->left, edge1->right); }else{ if(edge2->right) edge2->right->par = nullptr; join(edge1->left, edge2->right); } delete edge1; delete edge2; } bool IsConnected(BSTNode *ver1, BSTNode *ver2) noexcept { splay(ver1), splay(ver2); return ver1->par; } T& get(BSTNode *ver) noexcept { return splay(ver)->value; } void range(BSTNode *edge1, BSTNode *edge2, const T& val) noexcept { auto res1 = split_lower_bond(edge1); auto res2 = split_upper_bond(edge2); BSTNode::opr1(res2.first->lazy, val); join(join(res1.first,res2.first), res2.second); } T query(BSTNode *edge1, BSTNode *edge2) noexcept { auto res1 = split_lower_bond(edge1); auto res2 = split_upper_bond(edge2); T res = res2.first->al; return join(join(res1.first,res2.first), res2.second), res; } public: int V; BSTNode** vertex_set; map*> edge_set; EulerTourTree(const vector& ver_value, bool helper=false) noexcept : V((int)ver_value.size()){ vertex_set = new BSTNode*[V]; for(int i = 0; i < V; i++) vertex_set[i] = new BSTNode(i, i, 1, ver_value[i]); if(helper) G.resize(V); } void reroot(const int node_id) noexcept { reroot(vertex_set[node_id]); } void link(const int node1_id, const int node2_id) noexcept { link(vertex_set[node1_id], vertex_set[node2_id]); } void cut(const int ver_id, const int par_id){ auto it1 = edge_set.find((edge){ver_id, par_id}); auto it2 = edge_set.find((edge){par_id, ver_id}); assert(it1 != edge_set.end()); cut(it1->se, it2->se); } bool IsConnected(const int node1_id, const int node2_id) noexcept { return IsConnected(vertex_set[node1_id], vertex_set[node2_id]);} T& get(int ver_id){ return get(vertex_set[ver_id]); } void component_range(const int ver_id, const T& val){ range(ver_id, -1, val); } void range(const int ver_id, const int par_id, const T& val){ if(par_id < 0) return BSTNode::opr1(splay(vertex_set[ver_id])->lazy, val); auto it1 = edge_set.find((edge){par_id, ver_id}); auto it2 = edge_set.find((edge){ver_id, par_id}); assert(it1 != edge_set.end()); range(it1->se, it2->se, val); } T component_query(const int ver_id){ return query(ver_id, -1); } T query(const int ver_id, const int par_id){ if(par_id < 0) return splay(vertex_set[ver_id])->al; auto it1 = edge_set.find((edge){par_id, ver_id}); auto it2 = edge_set.find((edge){ver_id, par_id}); assert(it1 != edge_set.end()); return query(it1->se, it2->se); } // ヘルパー関数 vector > G; void add_edge(const int u, const int v){ G[u].push_back(v), G[v].push_back(u); } void dfs(const int u, const int p, const BSTNode *cur, vector& parent, vector*>& nodes){ parent[u] = p; nodes.push_back(vertex_set[u]); for(auto& v : G[u]){ if(v != p){ BSTNode* e1 = new BSTNode(u, v); edge_set[(edge){u, v}] = e1; nodes.push_back(e1); dfs(v, u, cur, parent, nodes); BSTNode* e2 = new BSTNode(v, u); edge_set[(edge){v, u}] = e2; nodes.push_back(e2); } } } vector build(const int _root){ vector parent(V, -1); vector* > nodes; BSTNode *cur = nullptr; dfs(_root, -1, cur, parent, nodes); int i, n = (int)nodes.size(), st = 2, isolate = ((n % 4 == 1) ? (n-1) : -1); while(st <= n){ for(i = st-1; i < n; i += 2*st){ nodes[i]->left = nodes[i-st/2], nodes[i-st/2]->par = nodes[i]; if(i+st/2 < n) nodes[i]->right = nodes[i+st/2], nodes[i+st/2]->par = nodes[i]; else if(isolate >= 0) nodes[i]->right = nodes[isolate], nodes[isolate]->par = nodes[i]; nodes[i]->eval(); } isolate = ((n % (4*st) >= st && (n % (4*st) < 2*st)) ? (i-2*st): isolate); st <<= 1; } return parent; } private: void check_dfs(BSTNode* cur){ cur->push(); if(cur->left) check_dfs(cur->left); cout << "{" << (cur->from) << "," << (cur->to) << "," << (cur->value) << "}" << endl; if(cur->right) check_dfs(cur->right); } }; #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(int n) { short res[10], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } int r[MAX_N]; int main() { int n = in(); rep(i,n) r[i] = in(); EulerTourTree et(vi(n, 0), true); rep(i,n-1){ int u = in(), v = in(); et.add_edge(u-1, v-1); } auto par = et.build(0); rrep(i,n){ et.component_range(i, 1); for(auto& to : et.G[i]){ if(to < i) et.cut(to, i); } } int ans = 1; rep(i,n){ ans = (ll)ans * (et.get(i) + r[i]) % MOD; } out(ans); return 0; }