Codeforces Round #746 Hemose in ICPC ? 题解 (Java/C++)

题解

首先,因为gcd(a,b,c)一定小于等于gcd(a,b)或者gcd(b,c)的。因此,这个最大距离必然就是最大的那一条边。

于是不难想到,我们第一次查询所有的点,得到整个树中最大的边的边权。接着二分搜索所有边,如果这一半的边中包含最大的边权,那么就继续在这一半中二分搜索,否则在另一半中二分搜索。

现在的问题就是怎么恰好找出一半的边来查询。

首先我们注意到最后的结果必然是相邻的两个点,且这两个点之间的边权是最大。而我们可以注意到,相邻的两个点必然其中一个是儿子而另外一个是父亲。
于是我们只需要找到这样的一个点,使这个点满足这个条件:这个点到这个点的父节点之间的边权是最大的。

于是就很自然了,我们重新对所有点按照从根向下依次编号(如下图所示)。我们只需要在[1,n-1]的范围内进行二分查找即可(显然,查找时需要包含目标的点的父亲,比如目标是[1,2,3]时,我们需要查询[0,1,2,3]这4个点的id)。

代码

Java

Submission #131278200 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #131279050 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论