P12255 [蓝桥杯 2024 国 Java B] 园丁

小明是一位尽职尽责的园丁。这天他负责维护一棵树，树上有 $n$ 个结点 $1, 2, \ldots, n$，根结点为 $1$，结点 $i$ 的权值为 $a_i$。他需要更改一些结点的权值为任意正整数，使得对于任意一个至少有 $2$ 个儿子结点的结点 $i$ 满足：任意两个 $i$ 的儿子结点的权值的乘积都不是完全平方数。请问小明至少需要修改多少个结点的权值？

输入共 $n+1$ 行。 第一行为一个正整数 $n$。 第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \ldots, a_n$。 后面 $n-1$ 行，每行两个正整数表示树上的一条边。

输出共 $1$ 行，一个整数表示答案。

### 样例说明 其中一种方案：将结点 $2, 5$ 的权值分别修改为 $3, 2$。 ### 评测用例规模与约定 - 对于 $20\%$ 的评测用例，保证 $n \leq 10^3$。 - 对于 $100\%$ 的评测用例，保证 $1\leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。