CF1916G 题解

· · 题解

题目做法

描述一下官方题解的做法：路径问题考虑点分。首先只考虑每个分治重心直上直下的链算一遍答案 ans_0，由 \min\{\gcd(rt,u),\gcd(rt,v)\}\ge \gcd(u,v) 可以知道 ans\leq 2ans_0。

然后据此再点分一遍，只考虑 2\times len(rt,u)\times \gcd(rt,u)\ge ans_0 的链即可，注意到能更新答案的两条链（不妨设 len(rt,u)\leq len(rt,v)）一定满足：

那么 std 声称，对每种 \gcd=g 的链保留最大与次大（不同子树）的 len，若其有可能更新答案，则依次枚举另一条 \gcd\in \{g,2g,\dots,len\times g\} 的最长链更新答案就能通过本题。

复杂度分析

谴责一下：赛前分析不出来 std 的复杂度就敢出题实在太逆天了。

赛后官方题解给出了 O(n\sqrt n\log n) 的巨大上界，但事实上有人教我了如何分析出 O(n\log^2 n) 的优秀时间复杂度，即下面我们要证明每层点分的枚举量为 O(n\log n)。

对于一个 size=sz 的点分重心 rt，记 dep_u=len(rt,u),mdep_u=\max \{dep_v|v\in subtree_u\}。我们把所有满足 dep_i=2^k,mdep_i\ge 2^{k+1}的点称作关键点，并将每个点 i 按照其祖先中 dep=2^{\lfloor\log_2(dep_i)\rfloor-1} 的关键点 u 分为若干组，每组点记作 S(u,dep_u,\gcd(rt,u))。

此时容易发现每个点都恰属于一组，且形如 S(u,2^k,g) 的组不超过 \dfrac{s}{2^k} 个。

又对于每个 i\in S(u,2^k,g)，其只有当 \gcd(rt,i)> \dfrac{g}{4} 时才需要被枚举（否则取 u 作为链的端点不劣，因为 dep_u>\dfrac{dep_i}{4}）——而这意味着每组内需要被枚举的点只有 O(1) 个。故每个 S(u,2^k,g) 只会造成枚举 O(d) 的枚举量，故由前文可知每种 k 仅会造成 O(n) 的枚举量，于是每层总枚举量 O(n\log n)，这与预处理 \gcd 的时间复杂度相同。

于是得到总时间复杂度 O(n\log^2n)，可以通过本题。