Optimizations From Chelsu

题意

给定 \(n\) 个结点的树，边有正整数边权 \(w_i\)。定义 \(len(u,v)\) 表示 \(u\) 到 \(v\) 的路径的边数，\(\gcd(u,v)\) 表示 \(u\) 到 \(v\) 的路径上所有边权的 \(\gcd\)，特别地 \(\gcd(u,u)=0\)。对于所有 \(u,v\in[n]\)，求 \(\max (len(u,v)\times \gcd(u,v))\)。

大致思路

我们考虑共用一个顶点的两条链对答案的更新情况，令他们长度，gcd，分别为 \(len_1,len_2,g_1,g_2(len_1\ge len_2)\)，我们发现只有满足以下几个条件才能更新答案：
1. \(gcd(g_1,g_2)=g_1\)，不然的话 \(gcd(g_1,g_2)\le \frac{g_1}{2}\)
2. \(g_2\le len_1\times g_1\)
推导： 设\(g_2=k\times g_1\)能贡献答案当且仅当 \(g_1\times(len_1+len_2)\ge g_1\times k\times len_2\rightarrow (k-1)\times g_1\times len_2\le g_1\times len_1\)

于是我们可以考虑淀粉质，枚举重心之后，对于每个 \(g\)，求出其最长链的长度 \(len\) ，然后枚举 \(k(k\le len)\) ，求出 \(g_2\) 更新答案即可