#P12255. [蓝桥杯 2024 国 Java B] 园丁
[蓝桥杯 2024 国 Java B] 园丁
题目描述
小明是一位尽职尽责的园丁。这天他负责维护一棵树,树上有 个结点 ,根结点为 ,结点 的权值为 。他需要更改一些结点的权值为任意正整数,使得对于任意一个至少有 个儿子结点的结点 满足:任意两个 的儿子结点的权值的乘积都不是完全平方数。请问小明至少需要修改多少个结点的权值?
输入格式
输入共 行。
第一行为一个正整数 。
第二行为 个由空格分开的正整数 。
后面 行,每行两个正整数表示树上的一条边。
输出格式
输出共 行,一个整数表示答案。
6
1 2 9 8 4 4
1 2
1 3
1 4
2 5
2 6
2
提示
样例说明
其中一种方案:将结点 的权值分别修改为 。
评测用例规模与约定
- 对于 的评测用例,保证 。
- 对于 的评测用例,保证 ,。