题目内容

某科技公司有 $n$ 名员工，他们之间的汇报关系构成一棵树，即恰好有 $n-1$ 对直接上下级关系且整个结构连通。每位员工有一个正整数能力值 $a_i$。 公司希望组建项目搭档：若两名员工之间存在直接上下级关系，且他们能力值的乘积恰好是一个完全平方数（即存在整数 $x \ge 1$ 使得 $a_u imes a_v = x^2$），则这两名员工可以组成一对搭档。每名员工至多只能属于一对搭档。 求最多能有多少名员工成功组成搭档（被选入某对搭档）。

约束条件：

• 员工数量 $n$ 满足 $1 \le n \le 10^5$。
• 每个能力值 $a_i$ 均为正整数，且 $a_i \le 10^9$。
• 给定的上下级关系保证形成一棵树，节点编号从 $1$ 到 $n$。