如果这个数大于上一个数,那么保持这样显然是最优的.如果这个数小于前一个,我们二进制计算它至少需要几轮运算才能大于前一个.只取最大值,时间复杂度\(\mathcal O(n \log n)\).
考虑第二个问题.如果几个叶子节点的父亲相同,那么这些节点的连通边的权重也一定相同.不然随便填,就满意了.只需要数一数每个点的叶子数.
由于几个直径之间有相交部分,所以维护\(s1,s2\)分别表示相交部分周围的点.那么每个点的直径要么是常数,要么更大.如果没有变化,就在对应的集合上加点.如果改变,清除对应的集合,判断另一个集合的点,将距离加到新的直径上.容易证明复杂性是正确的.时间复杂度\(\mathcal O(n \log n)\).
转移方程:
可以发现图只有一种情况:即可以找到一点与三个联通块相连.
那么对于每个点,bfs 计算它与三个联通块的距离之和,取最小值即可.
考虑到 \(k\leq 10^9\),经验告诉我们直接上矩阵快速幂,毕竟这转移无需判断.