CF1592Ddfs序+二分
题目
交互题。
给出一棵树,点数<=1000,边权未知。你每次可以询问一个点集,会返回这些点集两两路径边权gcd的最大值。请你用至多12次询问确定两个点,使得他们之间的路径边权gcd即是最大值。
求解思路
这个点集的最大值,等价于路径上权值最大的一条边。也就是我们要找到最大边权的边。
$2^{12}>1000$。只需每次都排除掉半棵树,我们就可以以$O(logn)$的时间复杂度找到答案。
可以用dfs序对边标号,这样所有边就是连续的。每次询问一半的边,排除掉一半。
代码
1 |
|