Time Limit: 5000/2500 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Since both Stefan and Damon fell in love with Elena, and it was really difficult for her to choose. Bonnie, her best friend, suggested her to throw a question to them, and she would choose the one who can solve it.

**Suppose there is a tree with n vertices and n - 1 edges, and there is a value at each vertex. The root is vertex 1.** Then for each vertex, could you tell me how many vertices of its subtree can be said to be co-prime with itself?

NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.

NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.

There are multiply tests (no more than 8).

For each test, the first line has a number $n$ $(1 \leq n \leq 10^5)$, after that has $n-1$ lines, each line has two numbers a and b $(1 \leq a,b \leq n)$, representing that vertex a is connect with vertex b. Then the next line has n numbers, the $i^{th}$ number indicates the value of the $i^{th}$ vertex. Values of vertices are not less than 1 and not more than $10^5$.

For each test, the first line has a number $n$ $(1 \leq n \leq 10^5)$, after that has $n-1$ lines, each line has two numbers a and b $(1 \leq a,b \leq n)$, representing that vertex a is connect with vertex b. Then the next line has n numbers, the $i^{th}$ number indicates the value of the $i^{th}$ vertex. Values of vertices are not less than 1 and not more than $10^5$.

提交代码