有关消防一题中最优解一定在直径上的证明P2491[SDOI2011]消防P1099[NOIP2007提高组]树网的核题目描述在一颗\(n\)个节点的无根树中，找到一条不超过\(s\)的路径，使得图中所有点到此路径距离的最大值最小，图中边权非负分析若想将此题转化到树网的核，需要证明对于任意一条不在直径上的路径，都能在直径上找到更优解首先理解一个显然的结论：路径越长，结果越优证明以下过程中所用符号及其含义:\(f(i)\)表示从\(i\)出发不经过直径上的边所能到达的最长距离\((u,v)\)为树的直径,\(L\)为直径长度\((A,B)\)为所取不在直径上的路径\(d(i,j)\)为\(i\)与

应该都和我一样一下水了两题吧P2491[SDOI2011]消防P1099[NOIP2007提高组]树网的核题目描述在一颗\(n\)个节点的无根树中，找到一条不超过\(s\)的路径，使得图中所有点到此路径距离的最大值最小，图中边权非负分析若想将此题转化到树网的核，首先要证明对于任意一条不在直径上的路径，都能在直径上找到更优解首先理解一个显然的结论：路径越长，结果越优证明以下过程中所用符号及其含义:\(f(i)\)表示从\(i\)出发不经过直径上的边所能到达的最长距离\((u,v)\)为树的直径,\(L\)为直径长度\((A,B)\)为所取不在直径上的路径\(d(i,j)\)为\(i\)与\(j\

洛谷P3304[SDOI2013]直径题解题目链接题目分析第一部分好说，求直径，dfs或者DP都可以。第二部分，有一个定理，就是所有直径中点重叠。那么有两种情况一种是中点在一个节点上，那么显然这个点是每条直径的终点，也就是说直径的一半相等。从这个点出发dfs，找出所有最远点。如果只有两条，输出depth之和。否则求lca，lca的depth就是重叠的数量。另一种，中点在一条边上。从这个边出发，两侧分别dfs找最远，再分类讨论，有的求lca，有的输出。具体见代码即可。题解中还有其他思路：比如从一条直径上开始dfs（利用直径同侧长度一定相等的性质），还有两次dp求出总cnt和边cnt进行统计的，还