2000ms

Difficulty: 7

算法与标签>树形dp

会员或题库专享

请先，开通会员，可解锁完整内容。

开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库，可解锁完整内容。

开通会员

解题思路

本题可以拆分为三个依次解决的部分：

预处理节点特征类型
节点 $i$ 的特征类型定义为 $a_i$ 的不同质因子的个数。
若对每个 $a_i$ 暴力试除，时间复杂度 $O(n\sqrt{a_i})$ 较为极限。
利用线性筛预先处理出 $1$ 到 $10^7$ 内每个数的最小质因子 minp[x]，之后对每个 $a_i$ 反复除以 minp[a_i] 并用集合统计不同质因子，即可在 $O(\log a_i)$ 时间内完成特征类型计算。
将计算出的特征类型直接存回数组 $a$ 中，后续只关心特征类型是否相等。

题目内容

给定一棵以节点 $1$ 为根、共有 $n$ 个节点的树，每个节点 $i$ 拥有一个正整数的属性值 $a_i$ 。

定义节点 $i$ 的特征类型为 $a_i$ 的不同质因子的个数。例如， $6$ 的质因子为 $2$ 和 $3$ ，特征类型为 $2$ ； $4$ 的质因子只有 $2$ ，特征类型为 $1$ 。

如果树上的一条边 $(u,v)$ 连接的两个节点具有相同的特征类型，则称这条边为关键边。

你可以进行如下操作：任选一个节点 $x$ ，将从根节点 $1$ 到 $x$ 路径上的所有边进行一次激活。

你的目标是让所有关键边都至少被激活一次。请问最少需要多少次操作？若操作次数不为零，请按升序输出每次操作所选择的节点编号。