G. **小美的树上染色

小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。 小美想知道，自己最多可以染红多少个节点？

第一行输入一个正整数n，代表节点的数量。 第二行输入n个正整数ai，代表每个节点的权值。 接下来的n-1行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。 1\leq n \leq 10^5 ; 1\leq a_i \leq 10^9 ; 1\leq u,v \leq n

输出一个整数，表示最多可以染红的节点数量。

例子说明： 可以染红第二个和第三个节点。 请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。 因此，最多染红 2 个节点。