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

    ID: 13910 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>2024数论树的遍历素数判断,质数,筛法蓝桥杯国赛

[蓝桥杯 2024 国 Java B] 园丁

题目描述

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

输入格式

输入共 n+1n+1 行。

第一行为一个正整数 nn

第二行为 nn 个由空格分开的正整数 a1,a2,,ana_1, a_2, \ldots, a_n

后面 n1n-1 行,每行两个正整数表示树上的一条边。

输出格式

输出共 11 行,一个整数表示答案。

6
1 2 9 8 4 4
1 2
1 3
1 4
2 5
2 6
2

提示

样例说明

其中一种方案:将结点 2,52, 5 的权值分别修改为 3,23, 2

评测用例规模与约定

  • 对于 20%20\% 的评测用例,保证 n103n \leq 10^3
  • 对于 100%100\% 的评测用例,保证 1n1051\leq n \leq 10^51ai1091 \leq a_i \leq 10^9