题目描述

有 $n$ 个部落，编号为 $1$ 到 $n$。部落之间由 $n-1$ 条道路连接，形成一棵树。部落 $i$ 的战斗力为 $A_i$。

如果若干个部落在树上连通，并且存在一个大于 $1$ 的整数，能够整除这些部落的全部战斗力，那么这些部落可以组成一个联盟。

请求出一个联盟最多可以包含多少个部落。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $x,y$，表示部落 $x$ 和部落 $y$ 之间有一条道路。

最后一行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$，表示各部落的战斗力。

输出格式

输出一个整数，表示一个联盟最多可以包含的部落数量。

样例

3
1 2
2 3
20 15 9

2

5
1 2
1 3
2 4
2 5
10 8 9 12 10

4

10
4 1
1 3
3 8
8 7
7 9
3 5
4 2
9 6
8 10
10 20 5 40 25 12 9 35 15 6

6

数据范围与提示

• 对于 $15\%$ 的数据，$1 \le n \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$
• $1 \le A_i \le 10^9$
• 输入的道路保证构成一棵树