P3761 [TJOI2017]城市 注意到两个城市之间的最大交通费用就是树的直径。 考虑枚举删去哪一条边，假设删的是边u,vu,vu,v，那么我们发现直径可能有三种选择： 1.1.1.直径缩在蓝色子树里面。 2.2.2.直径缩在红色子树里面。 上面两种情况，我们都不能通过加边来缩短直径，是无法掌控的。 3.3.3.直径的一段在蓝色子树里面，另一端在红色子树里面，这时直径必定跨越边u,v...

传送门 扫了一眼题解，发现没有一个严谨证明的，那么我就来证明一波吧。 首先，我们看一看如何求树的直径： 1.1.1.随便定一个根节点，第一遍bfsbfsbfs求出树中深度最深的节点，记为uuu。 2.2 .2.以uuu为根节点，第二遍bfsbfsbfs求出树中深度最深的点vvv 3.3.3.树的直径的端点即为u,vu,vu,v 类比到此题： 我们把政党ppp中的牛最深的记为max⁡p\ma...