思路

分析油费公式 油费公式为 $F(d) = \frac{d(d+1)}{2} + 10d$ ，其中 $d$ 是行驶的公里数。我们可以将其化简： $F(d)$ = $\frac{d^2 + d + 20d}{2}$ = $\frac{d^2 + 21d}{2}$ 这是一个关于 $d$ 的二次函数。由于行驶距离 $d$ 总是正数，这个函数的导数 $F'(d) = d + 10.5$ 恒为正。这意味着油费 $F(d)$ 是一个单调递增函数：行驶的距离越长，油费就越高。
转化问题 因此，要找到最大的油费，我们只需要找到最长的连续行驶距离。在给定的城市网络中，任意两个城市之间的路径是唯一的。城市和道路构成了一个树形结构。问题就转化为了：求解树的直径。树的直径是指树中任意两个节点之间最长的路径长度。

P3707.第2题-快递员小李

1000ms

Difficulty: 3

所属公司 : 钉钉

算法与标签>BFS

小李是一名快递员，他负责在一个特殊的城市群里送快递。这个城市群有个特点:所有的城市都通过道路连接在一起，形成了一个树状的交通网络(就像一棵大树的分支一样)。这意味着:

$1.$ 任何两个城市之间都有且仅有一条路径相连 $2.$ 不会有环形路线，所有道路都是直线连接

问题描述:

小李发现了一个有趣的现象:他的快递车有个特殊的计费系统。当他连续驾驶不停车时，油费是这样计算的:

也就是说，如果小李要连续开车走 $n$ 公里，总油费就是: $11 + 12 + 13 + ... +(n+10)$ 元

现在小李想知道:在这个城市群中，他从任意一个城市出发，一口气开到另一个城市 (中途不停车加油)，最多需要花费多少油费?

第一行:一个数字n，表示城市总数(城市编号从 $1$ 到 $n$ ，其中 $1$ 号是主城区, $n$ 的范围 $(3<=n<=100000)$

接下来 $n-1$ 行:每行三个数字 $abc$ ，表示城市 $a$ 和城市 $b$ 之间有一条长度为c公里的道路

输出一个数字，表示小李可能花费的最大油费

输入

输出

输入

预期输出（选填）