P3761 [TJOI2017] 城市

从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有 $n$ 座城市，$n-1$ 条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。 小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路（即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？

无

无

对于 $30\%$ 的数据，$1\leq n\leq 500$。 对于 $100\%$ 的数据，$1\leq n\leq 5000$。