🔍 核心思路解析

题目条件可以简化理解为：每个节点的容量必须等于其所有子节点容量之和，且所有子节点的容量必须相等。这意味着：

• 如果确定任意一个节点的容量，整棵树的容量就都确定了。
• 题目求最少修改数量，等价于求最多有多少个节点在某个方案中可以保持原容量不变。

🧮 关键步骤与技巧

1. 确定容量关系 从条件可知，对于节点 ( u ) 和它的一个子节点 ( v )： [ A[u] = \text{deg}(u) \times A[v] ] 其中 ( \text{deg}(u) ) 是 ( u ) 的子节点个数。从根节点到任意节点 ( i )，其容量 ( A[i] ) 与根节点容量 ( A[1] ) 的关系为： [ A[i] = A[1] \times \prod \frac{1}{\text{deg}(p)} \quad (\text{p是i到根路径上的节点}) ] 因此，如果节点 ( i ) 的容量不变，根节点的容量必须为： [ RootValue(i) = A[i] \times \prod \text{deg}(p) ] 这个值巨大的原因在于连乘。

2. 处理大数：取对数 直接计算连乘会溢出。由于我们只关心哪些节点对应的根节点容量相同，可以利用对数将乘法转换为加法： [ \log(RootValue(i)) = \log(A[i]) + \sum \log(\text{deg}(p)) ] 这样，拥有相同 ( \log(RootValue(i)) ) 的节点，其对应的根节点容量也相同。我们只需统计出现次数最多的 ( \log(RootValue(i)) )，设其出现次数为 ( cnt_{max} )，则答案为 ( n - cnt_{max} )。

3. 算法流程

   • 预处理：构建树结构，计算每个节点的出度（子节点个数）。
   • DFS计算对数：从根节点开始DFS，计算每个节点到根路径上的 ∑log(deg(p))，然后加上 log(A[i])。
   • 统计答案：将所有 log(RootValue(i)) 排序，找出出现次数最多的值 ( cnt_{max} )，输出 ( n - cnt_{max} )。

💻 代码实现提示

• 使用 double 存储对数值通常精度足够。
• DFS时，传入当前累积的 sum_log_deg，每进入一个子节点，就加上 log(deg(u))。
• 注意根节点的处理：根节点没有父节点，其度就是子节点个数。

💎 总结与提示

这道题的核心在于转化思维：将复杂的约束条件转化为节点间的容量关系，并通过取对数巧妙地解决了数值溢出问题。