CF1294F 题解

在这里插入图片描述
看到大佬们都是用的 $O (n)$ 的做法，本蒟蒻不会，就按合情合理的思路写了一个 $O(n\log n)$ 的做法。

首先可以确定，其中的两个点肯定是直径的两个端点。感性理解一下，如果不是的话，那么把其中的点换成直径的一个端点，答案一定不会更差，因为直径已经是树上的最长路径了。然后问题就变成了在树上找到一个点，使它到直径的两个端点的路径和直径的并所经过的边数最多。我们考虑一个简单的不能算容斥的容斥。

在这里插入图片描述
拿这棵树来说，假如直径的两个端点是 $1$ 和 $6$ ，我们要找 $5$ 这个点，那么分别记录下来直径的两个端点到其余点的距离，然后我们将其中的一个端点设为根，把其余点的深度和求 $l c a$ 用的数组预处理出来。那么我们可以求出 $5$ 和深度较深的那个端点的 $l c a$ ，然后就是一个小的容斥，假设两个端点到 $5$ 的距离分别为 $d i s 1$ 和 $d i s 2$ ，那么答案就是 $d i s 1 + d i s 2 + d$

相关阅读:
Java获取当前时区时间LocalDateTime与System.currentTimeMillis
浅析vue3PDF插件不显示文字
一类综合的模糊化自适应滑模控制
JDBC-02：操作访问数据库时使用Statement操作数据表的弊端
search——single list
ARMv7-A 那些事 - 5.CP15协处理器
在线客服系统源码开发实战总结：需求分析及前端代码基本技术方案
halcon 矩形相似度 rectangularity
若依（ruoyi）管理系统（前后端分离版）本地运行教程（Windows）
做外贸必知——你还不知道外贸拼箱技巧吗

原文地址：https://blog.csdn.net/glorious_dream/article/details/127655880