小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。 小美想知道，自己最多可以染红多少个节点？
第一行输入一个正整数 n ，代表节点的数量。 第二行输入 n 个正整数 a_i ，代表每个节点的权值。 接下来的 n-1 行，每行输入两个正整数 u,v ，代表节点 u 和节点 v 有一条边连接。 1≤ n ≤ 10^5 1≤ a_i ≤ 10^9 1≤ u,v ≤ n
输出一个整数，表示最多可以染红的节点数量。
3 3 3 12 1 2 2 3
2
考点：树
数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：树
本题切入点
两节点权值乘积为完全平方数等价于去掉平方因子后二者相等；在树上做最大匹配（树形 DP），每匹配一对就染红两个节点。
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 3 / 3 3 12 / 1 2 / 2 3 → 输出 2
可以染红第二个和第三个节点。
请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。
因此，最多染红 2 个节点。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2023年美团秋招编程岗第一批笔试。