题解：CF1592D Hemose in ICPC ?

Wyh_dailyAC · 2025-12-15 18:53:58 · 题解

题意

略。

思路

首先，对于正整数集合 S' 与 S，如果 S' \subset S，那么 S 内的元素的 \gcd 对比 S' 内元素的 \gcd 一定是不会更优（数值大）的。

那么可得最优解一定是一条树边。

又易得，一个连通块内的连续路径的最大 \gcd 一定是这个连通块的某一条边（易证）。

我们还看到询问最高次数为 12，这很 \log 啊！

所以可得算法标签：二分。

二分什么呢？我们二分出一个包含原树根节点的连通块，这可以在原树的 DFS 序上完成（原树 DFS 序的一个前缀所对应于原图的一个子图，就是一个包含原树根节点的连通块）。

所以最终的算法步骤：

• 一：求一遍全局最大 \gcd
• 二：二分 DFS 序前缀以二分到最大权值边的较深端点
• 三：得到最大权值边的端点。

Code

没写。