自动搬运

查看原文

来自洛谷，原作者为

	ErgouTree **

搬运于2025-08-24 23:14:04，当前版本为作者最后更新于2025-04-24 20:33:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

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

思路

完全平方数的判定

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

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

例如 $4 \times 9 = 36$ 是完全平方数，因为 $4 = 2 ^ 2,9 = 3 ^ 2$ ，他们的质因子的幂次都是偶数。

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

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

代码处理

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

贪心处理：

对每个有 $k \ge 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;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

class Solutions {
    private int n ,ans = 0;     // 树中节点的数量
    private int[] a = new int[100086];   // 节点值
    private int[] f = new int[100086];   // 节点值的平方自由部分
    private List<Integer>[] tree;   // 邻接表表示树

    // 返回 x 的平方自由部分
    // 平方自由部分是指一个数分解质因数后，每个质因数的指数都为 1 的部分
    private int squareFree(int x) {
        int res = 1;
        for (int i = 2; i * i <= x; i++) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            if ((cnt & 1) == 1) res *= i;  // 如果质因数的幂次为奇数，将其乘到结果中
        }
        if (x > 1) res *= x;   // 如果 x 还有剩余的质因数，也乘到结果中
        return res;
    }

    private void dfs(int u, int fa) {
        List<Integer> children = new ArrayList<>();
        // 遍历当前节点 u 的所有邻接节点 v
        for(int v: tree[u]) {
            // 不是父节点，加入children
            if(v != fa){
                children.add(v);
                dfs(v, u);   // 递归调用
            }
        }
        if (children.size() >= 2) {
            // 统计每个子节点的平方自由部分的出现次数
            Map<Integer, Integer> cnt = new HashMap<>();
            for(int v: children){
                cnt.put(f[v], cnt.getOrDefault(f[v], 0) + 1);
            }
            for (int c : cnt.values()) {
                if (c > 1) ans += c - 1;
            }
        }
    }

    public Solutions(){
        FastReader sc = new FastReader();
        n = sc.nextInt();
        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);
        }
        // 从根节点（节点 1）开始进行深度优先搜索
        dfs(1, 0);
        // 输出最终结果
        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());
        }
    }
}

但是，上述代码会出现递归调用过深的问题，我们需要将原来的递归深度优先搜索（DFS）改为迭代方式。通过使用栈来模拟后序遍历，我们可以避免递归调用过深的问题。

//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());
        }
    }
}