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$

相关阅读:
Nginx 面试题
【无标题】
Appium学习日记（一）——Appium工作原理及其主要组件
Nautilus Chain上线主网，为DeFi和流支付的未来构建基础
Python数据分析实战-实现卡方检验（附源码和实现效果）
搭建一个属于自己的博客
JUC-无锁
IOS恢复
设计模式——解释器模式
vue 自定义指令简单记录

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