第十五届蓝桥杯Java国赛B组D题-园丁题解

题目大意

题目的核心是要处理一棵树上每个节点的权值，对于拥有两个及以上儿子节点的父节点，要保证所有儿子节点的权值两两相乘不能是完全平方数，目标是求出最少需要修改多少个节点的权值，才能让整棵树满足这个条件。

思路

完全平方数的判定

首先什么是完美平方数，如果一个正整数 a 是某一个整数 b 的平方，那么这个正整数 a 叫做完全平方数。零也可称为完全平方数。

两个数 x 和 y 的乘积是完全平方数，当且仅当 x 与 y 的乘积中，所有质因子的幂次都是偶数。

例如 4 * 9 = 36 是完全平方数，因为 4 = 2²，9 = 3² ，他们的质因子的幂次都是偶数。

进一步推导，这个条件等价于 x 和 y 的 “平方因子化简后” 的形式相同。所谓 “平方因子化简”，就是对每个数 a 分解质因数后，只保留每个质因数的奇数次幂（即 a_i 的“平方自由部分”），这部分记作 f(a_i)。

若 f(a_i) = f(a_j) ，那么 a_i * a_j 必然是完全平方数。

代码处理

使用邻接表存树，如果存在两个儿子节点的 f(a_j) 相等，那么这两个儿子节点权值的乘积就是完全平方数，不满足题目要求。

贪心处理：

对每个有 k ≥ 2 个儿子的结点 i，统计其所有儿子的 f(a_j)，对于重复的 f(a_j)，需要修改其中 cnt − 1 个结点的权值（cnt 为该 f(a_j) 出现次数）。对每个结点，累加需要修改的次数。

关于squareFree(int x) — 求平方自由部分:
我们需要只保留不能被2整除的幂次部分，所以按照如下形式解耦出平方自由部分

private int squareFree(int x) {
    int res = 1;
    for (int i = 2; i * i <= x; i++) { // 枚举所有可能的质因数
        int cnt = 0;
        while (x % i == 0) { // 统计i作为质因子的次数
            x /= i;
            cnt++;
        }
        if ((cnt & 1) == 1) res *= i; // 只保留奇数次的质因数
    }
    if (x > 1) res *= x; // x本身是大于1的质数
    return res;
}

完整代码如下

//package 数学.subject.P12255_蓝桥杯2024国JavaB_园丁;

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        new Solutions2();
    }
}


class Solutions2{
    private int n;
    private int[] a;
    private int[] f;
    private List<Integer>[] tree;
    private int ans = 0;

    private int squareFree(int x) {
        int res = 1;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                int cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }
                if (cnt % 2 != 0) {
                    res *= i;
                }
            }
        }
        if (x > 1) {
            res *= x;
        }
        return res;
    }

    public Solutions2(){
        FastReader sc = new FastReader();
        n = sc.nextInt();
        a = new int[n + 1];
        f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            f[i] = squareFree(a[i]);
        }

        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            tree[u].add(v);
            tree[v].add(u);
        }

        // 使用迭代的后序遍历来替代递归DFS
        Deque<Object[]> stack = new ArrayDeque<>();
        stack.push(new Object[]{1, 0, false});

        while (!stack.isEmpty()) {
            Object[] node = stack.pop();
            int u = (Integer) node[0];
            int fa = (Integer) node[1];
            boolean visited = (Boolean) node[2];

            if (!visited) {
                stack.push(new Object[]{u, fa, true});
                List<Integer> children = new ArrayList<>();
                for (int v : tree[u]) {
                    if (v != fa) {
                        children.add(v);
                    }
                }
                // 逆序压入，以保持原来的处理顺序
                for (int i = children.size() - 1; i >= 0; i--) {
                    int v = children.get(i);
                    stack.push(new Object[]{v, u, false});
                }
            } else {
                List<Integer> children = new ArrayList<>();
                for (int v : tree[u]) {
                    if (v != fa) {
                        children.add(v);
                    }
                }
                if (children.size() >= 2) {
                    Map<Integer, Integer> cnt = new HashMap<>();
                    for (int v : children) {
                        int sf = f[v];
                        cnt.put(sf, cnt.getOrDefault(sf, 0) + 1);
                    }
                    for (int c : cnt.values()) {
                        if (c > 1) {
                            ans += c - 1;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }

    class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
        String next() {
            while (!st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}