1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 200010;
const long long mod = 1e9 + 7;
namespace IO {
const int_fast32_t MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
template<typename type>
inline type read() {
type x = 0, f = 1;
char c = gc();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = gc();
}
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
inline void write(int_fast32_t x) {
static int_fast32_t sta[35];
int_fast32_t top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
} // namespace IO
using namespace IO;
long long n;
bool vis[maxn], chosen[maxn];
struct PNT {
long long w, id;
} p[maxn];
bool cmp(PNT a, PNT b) {
return a.w > b.w;
}
struct EDGE {
long long to, nxt;
} edge[maxn * 2];
long long head[maxn], tote;
void addEdge(long long from, long long to) {
edge[++tote].to = to;
edge[tote].nxt = head[from];
head[from] = tote;
}
long long dp[maxn][2];
long double sum[maxn][2];
void dodp(long long rt, long long fa) {
dp[rt][0] = 1; dp[rt][1] = p[rt].w;
sum[rt][0] = 0; sum[rt][1] = log2(p[rt].w);
for (long long i = head[rt]; i; i = edge[i].nxt) {
long long to = edge[i].to;
if (to == fa) continue;
dodp(to, rt);
if (sum[to][1] > sum[to][0]) {
dp[rt][0] = dp[rt][0] % mod * dp[to][1] % mod;
sum[rt][0] = sum[rt][0] + sum[to][1];
} else {
dp[rt][0] = dp[rt][0] % mod * dp[to][0] % mod;
sum[rt][0] = sum[rt][0] + sum[to][0];
}
dp[rt][1] = dp[to][0] % mod * dp[rt][1] % mod;
sum[rt][1] = sum[to][0] + sum[rt][1];
}
}
long long maxx;
int main() {
n = read<long long>();
For(i, 1, n) {
p[i].w = read<long long>();
}
For(i, 1, n - 1) {
long long u, v;
u = read<long long>();
v = read<long long>();
addEdge(u, v);
addEdge(v, u);
}
dodp(1, 1);
if (sum[1][0] > sum[1][1]) cout << dp[1][0] % mod << endl;
else
cout << dp[1][1] % mod << endl;
return 0;
}
|